資料結構------線段樹2：單點修改與區間詢問

上一次我們講到線段樹的概念和建樹，今天，我們來講線段樹的單點修改與區間詢問。

1.單點修改

單點修改會改變它所在子樹的節點，當你修改了葉節點後，一定要更新其祖先的值。

code:

void up(int p){
    s[p] = s[p * 2] + s[p * 2 + 1];
}//向上更新節點
void modify(int p, int l, int r, int x, int v){//p節點編号，l，r區間，v修改值
    if (l == r){
        s[p] += v;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        modify(p * 2, l, mid, x, v);//左子樹
    else
        modify(p * 2 + 1, mid + 1, r, x, v);//右子樹
    up(p);
}      

其實這就是一個模闆，記一下，對你有好處！

2.區間詢問

一般來說，區間詢問是以這樣的形式出現滴：

給定一個區間 [ l , r ] ,求區間的和。

上圖QAQ

線段樹：我又回來啦！

此時，詢問 [ 3 , 6 ]的最小值。

先找3所在的區間 [ 1 , 5 ] ,接着在搜左子樹，右子樹。直到搜到3。

之後在3~6的區間中，[ 4 , 5 ]是一個節點，直接傳回區間最小值，不必往下搜，再到右子樹上去搜6，找到總區間最小值。

1 int query(int p, int l, int r, int x, int y)
 2 {
 3     if (x <= l && r <= y) return s[p];//若該結點被查詢區間包含
 4     int mid = (l + r) / 2, res = 0;
 5     if (x <= mid) 
 6     res += query(p * 2, l, mid, x, y);
 7     if (y > mid) 
 8     res += query(p * 2 + 1, mid + 1, r, x, y);
 9     return res;
10 }      

這要用到之前的修改

這就是線段樹的單點修改與區間查詢

自己背一背模闆，rp++。