线段树 (区间查询)

結構

線段樹是一個平衡的二元樹，所有葉子到根的距離最多只差1。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內部結點代表的區間為其兩個兒子代表區間的聯集。

基本操作

線段樹所要提供的是查詢一個區間內的資訊，並允許修改操作。要使用線段樹，此資訊必須滿足對於區間與位於區間內的一點，要可以由、求得。例如範圍最值查詢即符合此條件。
代碼中, rt指的是root, 當前子樹的根節點; l, r指的是當前子樹所統計的區間利用完全二元堆積的性質來儲存節點編號, 所以rt << 1是左子樹的節點, rt << 1 | 1是右子樹的節點在查詢和成端更新操作中的L和R是指修改或者查詢的區間

節點資料向上更新

將子節點的值更新到父節點。
/* 对于区间求和 */void push_up(int rt) {
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];}/* 对于区间求最大值 */void push_up(int rt) {
    tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);}

節點懶惰標記下推

對於區間求和, 原子陣列值需要加上lazy標記乘以子樹所統計的區間長度。
len為父節點統計的區間長度, 則len - (len >> 1)為左子樹區間長度, len >> 1為右子樹區間長度。
void push_down(int rt, int len) {
    tree[rt << 1] += lazy[rt] * (len - (len >> 1));
    lazy[rt << 1] += lazy[rt];
    tree[rt << 1 | 1] += lazy[rt] * (len >> 1);
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;}
對於區間求最大值, 子樹的值不需要乘以長度, 所以不需要傳遞參數len。
void push_down(int rt) {
    tree[rt << 1] += lazy[rt];
    lazy[rt << 1] += lazy[rt];
    tree[rt << 1 | 1] += lazy[rt];
    lazy[rt << 1 | 1] += lazy[rt];
    lazy[rt] = 0;}

建樹

新建一棵長度N的線段樹。
#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rvoid build(int rt = 1, int l = 1, int r = N) {
    if (l == r) { std::cin >> tree[rt]; return; }
    int m = (l + r) >> 1;
    build(lchild); build(rchild);
    push_up(rt);}

更新

單點更新, 不需要用到lazy標記
#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rvoid update(int p, int delta, int rt = 1, int l = 1, int r = N) {
    if (l == r) {
        tree[rt] += delta;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, delta, lchild);
    else update(p, delta, rchild);
    push_up(rt);}
成段更新, 需要用到lazy標記來提高時間效率
#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rvoid update(int L, int R, int delta, int rt = 1, int l = 1, int r = N) {
    if (L <= l && r <= R) {
        tree[rt] += delta * (r - l + 1);
        lazy[rt] += delta;
        return;
    }
    if (lazy[rt]) push_down(rt, r - l + 1);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, delta, lchild);
    if (R > m)  update(L, R, delta, rchild);
    push_up(rt);}

區間查詢

#define lchild rt << 1, l, m#define rchild rt << 1 | 1, m + 1, rint query(int L, int R, int rt = 1, int l = 1, int r = N) {
    if (L <= l && r <= R) return tree[rt];
    if (lazy[rt]) push_down(rt, r - l + 1);
    int m = (l + r) >> 1, ret = 0;
    if (L <= m) ret += query(L, R, lchild);
    if (R > m)  ret += query(L, R, rchild);
    return ret;}

可直接使用的編程模板

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>using namespace std;namespace SegTree {
#define maxn 1000000
class SegmentTree {
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
public :
int addv[maxn], maxv[maxn], minv[maxn], sumv[maxn];
int arr[maxn];
int N;
private:int _max(const int& _, const int& __) { return _>__?_:__; }
private:int _min(const int& _, const int& __) { return _<__?_:__; }
public : int pushup(int o) {
minv[o] = _min(minv[lson], minv[rson]);
maxv[o] = _max(maxv[lson], maxv[rson]);
sumv[o] = sumv[lson] + sumv[rson];
return 0;
}
public : int pushdown(int o, int l, int r) {
if(addv[o] == 0) return -1;
addv[lson] += addv[o]; addv[rson] += addv[o];
minv[lson] += addv[o]; minv[rson] += addv[o];
maxv[lson] += addv[o]; maxv[rson] += addv[o];
sumv[lson] += addv[o] * (mid-l+1); sumv[rson] += addv[o] * (r-mid);
addv[o] = 0;
}
public : int Build(int o, int l, int r) {
addv[o] = 0;
if(l == r) {
maxv[o] = arr[l];minv[o] = arr[l];sumv[o] = arr[l];
return 0;
}
Build(lson, l, mid);
Build(rson, mid+1, r);
pushup(o);
return 0;
}
public : int optadd(int o, int l, int r, int ql, int qr, int addval) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
addv[o] += addval;
sumv[o] += addval * (r-l+1);
return 0;
}
pushdown(o, l, r);
optadd(lson, l, mid, ql, qr, addval);
optadd(rson, mid+1, r, ql, qr, addval);
pushup(o);
}
public : int query_sum(int o, int l, int r, int ql, int qr) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
return sumv[o];
}
pushdown(o, l, r);
return query_sum(lson, l, mid, ql, qr) + query_sum(rson, mid+1, r, ql, qr);
}
public : int query_min(int o, int l, int r, int ql, int qr) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
return minv[o];
}
pushdown(o, l, r);
return _min(query_min(lson, l, mid, ql, qr), query_min(rson, mid+1, r, ql, qr));
}
public : int query_max(int o, int l, int r, int ql, int qr) {
if(ql > r or qr < l) return 0;
if(ql <= l and r <= qr) {
return maxv[o];
}
pushdown(o, l, r);
return _max(query_max(lson, l, mid, ql, qr), query_max(rson, mid+1, r, ql, qr));
}
};} 
//End of SegmentTreeusing namespace SegTree;

變種

zkw線段樹是一種自底向上的線段樹，由清華大學的張昆瑋提出。它相對於傳統線段樹的優勢體現在減少了遞迴操作和增加了位運算等操作以減少常數。

相關連結

http://dongxicheng.org/structure/segment-tree/