【筆記】Segment Tree 線段樹

  • 【用途】多次查詢區間 [L, R] 的某些資訊,如「區間和」或「區間最大值」。 亦可同時紀錄多種資訊。 資料可以修改 (單點修改或區間修改)。
  • 【條件】要查詢的資訊需滿足「結合律」。
  • 【實作】
    • 二元樹資料結構 (根節點編號為1)。
    • 每個節點存一段連續區間 [L, R] 的資訊(e.g. 區間和),如節點 [1, 2] 存放A1 + A2。
    • 根節點存放區間 [1, n] 的資訊。(下圖假設有n = 9筆資料)
    • 節點編號:每個點的左兒子的節點編號為 x*2 (x<<1) ,右兒子則為 x * 2 + 1 (x<<1|1) 。
    • 陣列 total[n << 2]:存放每段區間的數字總和(開4倍陣列避免溢位。)
    • build( ):建立線段樹,左子樹紀錄區間 [L, mid],右子樹紀錄區間 [mid+1, R]。
    • pull( ):合併左節點與右節點的值。
    • query( ):查詢對應區間 [ql, qr] 的值。
    • update( ):更新單點 (位置pos) 的值 (val),所有重疊的區間都要一併更新。
  • 【練習】HDU 1166. 敌兵布阵題解
//total:線段樹的每個節點,用來紀錄區間和
//開4倍陣列避免溢位
int total[50005 << 2];

void pull(int x){
    //合併左節點與右節點
    total[x] = total[x<<1] + total[x<<1|1];
}

void build(int x, int l, int r){
    if (l == r){
        cin >> total[x];
        return;
    }
    int mid = (l+r) >> 1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    pull(x);
}

int query(int x, int l, int r, int ql, int qr){
    //[ql, qr]: 查詢區間
    if (ql <= l && qr >= r){
        return total[x];
    }
    int ret = 0;
    int mid = (l+r)>>1;
    if (ql <= mid){
        ret += query(x<<1, l, mid, ql, qr);
    }
    if (qr > mid){
        ret += query(x<<1|1, mid+1, r, ql, qr);
    }
    return ret;
}

void update(int x, int l, int r, int pos, int val){
    if (l == r){
        total[x] += val;
        return;
    }
    int mid = (l+r) >> 1;
    if (pos <= mid) update(x<<1, l, mid, pos, val);
    else update(x<<1|1, mid+1, r, pos, val);
    pull(x);
}

【更多練習】HDU 1754. I Hate It題解
【更多練習】HDU 3308. LCIS題解
【更多練習】HDU 4027. Can you answer these queries?題解

分享本文 Share with friends