線段樹Segment Tree

李知易

特色：線段樹是一種二元樹形的資料結構，可以快速查詢結構內包含某一點的所有區間
常見應用：點修改、區間修改、區間查詢（區間求和，求區間最大值，求區間最小值）
建構線段樹：
(pseudo code)
array segment_tree; //用來存線段樹的那個陣列，用普通陣列或vector都可
array a; //序列
int n; //a的大小

//v的區間是[L,R]
void build(int L, int R, vertex v){
    if(L == R){
        segment_tree[v] = 用a[L]得出答案;
        return;
    }
    int M = (L + R) / 2;
    //把區間二等分
    build(L, M, v的左子節點);
    build(M + 1, R, v的右子節點);
}