Segment Tree 2

使用線段樹通常有兩個條件

當前節點維護的資訊可以從左右子節點得到
操作有結合率

就能用線段樹維護

例題：CSES: Polynomial Queries

給一個長度為 n 的整數序列，和 m 筆操作
操作分兩種

\(\text{0 l r}\) : 將區間 [l, r] 範圍的元素 \(a_l\) 加 1， \(a_{l+1}\) 加 2 … 以此列推
\(\text{1 l r}\) : 詢問區間 [l, r] 的總和

至於這題要如何維護呢？ 🥴

詢問為求區間總和，
因此只需要把等差加值好好的處理就做完了

可以發現，我們對區間的加值會是一個從 1 開始、公差為 1 的等差數列，我們便可以維護這個性質，因為只要有首項、項數、公差，就可以在 \(O(1)\) 時間算出等差數列的總和（高中數學）。

項數就是那個區間的大小，而當一個等差數列疊加到另外一個等差數列上時

  1  2  3  4  5  6
+    1  2  3  4  5  6
_______________________
  1  3  5  7  9 11  6
     ‾  ‾  ‾  ‾ ‾‾

可以發現重疊的部分的首項跟公差就會變成兩者相加了！
中間重疊部分的公差直接就變成 2，我們只需要維護這些，就可以解出這題了。

懶人標記下推

下推時，右子區間的首項要再加上左子區間的長度*公差
first 陣列紀錄當前區間第一個元素(首項)要加值多少
diff 陣列紀錄公差

 int diff[MXN<<2], first[MXN<<2], seg[MXN<<2];
void push(int id, int l, int r){
    if(diff[id]){
        // (首項+末項) * 項次 / 2
        seg[id] += (first[id]*2 + (r-l)*diff[id]) * (r-l+1) / 2;
        if(l != r){
            diff[cl(id)] += diff[id];
            diff[cr(id)] += diff[id];
            first[cl(id)] += first[id];
            first[cr(id)] += first[id] + ((l+r)/2 - l + 1) * diff[id];
        }
        diff[id] = first[id] = 0;
    }
}

區間更新 –- 打懶人標記

由於每次加的首項固定是 1，因此遞迴時不需要傳遞加值的參數
打懶人標記時，再判斷跟加值左界差多少即可

 void update(int i, int l, int r, int ql, int qr){
    push(i, l, r); // 懶標下推
    if(ql <= l && r <= qr) {
        first[i] += (l - ql + 1); // 區間首項加的值為當前左界 - 詢問左界 + 1
        diff[i]++;
        return;
    }
    int mid = (l + r)>>1;
    if(ql <= mid)
        update(cl(i), l, mid, ql, qr);
    if(qr > mid)
        update(cr(i), mid + 1, r, ql, qr);
    pull(i, l, r); // 更新當前區間的總和
}

區間詢問

跟一般的總和線段樹沒什麼差別
seg 陣列一樣是儲存區間總和
不特別贅述

Range Updates and Sums

給一長度為 n 的整數序列，和 m 筆操作
操作分三種

\(\text{update l r v}\)，將序列的區間 [l, r] 加值 v
\(\text{update l r v}\)，將序列的區間 [l, r] 都設值成 v
\(\text{query l r}\)，詢問序列的區間 [l, r] 總和

\(n,m<10^5\)
多了一個區間設值

兩種操作單獨出現都可以解掉，但同時出現時要好好處理。

由於需要維護兩種懶標，我們還需要考慮同時有兩個懶標存在的情況。

兩個懶人標記 setTag 和 addTag
分別維護區間設值與區間加值

在維護標記時，可以分為 3 種情況

本來沒有任何標記，現在再加值/設值
本來有加值/設值標記，現在再加值
本來有加值/設值標記，現在再設值

1. 本來沒有任何標記，現在再加值/設值

那就跟一般加值/設值線段樹一樣
打上加值或設值標記就好

2. 本來有加值/設值標記，現在再加值

本來有加值標記，那再加值有疊加性，不影響
本來有設值標記再加值，可以先設值完之後再加值

3. 本來有加值/設值標記，現在再設值

區間設值則之前所有的標記都要不用理他了
直接把原本的加值/設值都清空，設上新的值

綜合以上的 case，只需要好好處理以下情況

更新區間時，同時有設值/加值標記時，先設值再加值
有設值操作時，到覆蓋的區間先把原有的設值/加值標記先清空，再放上設值標記

其他跟一般線段樹相同 !

把這份講義的內容好好理解完能自己刻出來的話，
理論上線段樹實做就不會有什麼問題了

夠熟的話也能跟講師一樣，無腦三分鐘內刻完區間修改線段樹

剩下的就是應付各種題目的題目變化
題目主要有兩種

轉換題意，配合基礎的加值/求區間總和或極值(題單的D)
維護的東西與平常不同，好好維護懶人標記以及合併(題單的C,E)

而 BIT 的 code 比 segment tree 短很多，
遇到資料結構題時，請先想一下 BIT 是否可做(區間修改/單點詢問 or 單點詢問/區間修改)

如果可以的話請不要沒事亂砸線段樹
實作量較大，bug 可能也比較多

題單

	void update(int id,int l,int r,int ql, int qr, int v){
	if(ql <= l && r <= qr){ //如果當前區間被更新區間完全覆蓋到
	tag[id] += v; //就打標記紀錄以下區間都要更新
	return;
	}
	int mid=(l+r)>>1;
	if(ql <= mid)
	update(cl(id),l,mid);
	if(qr > mid)
	update(cr(id),mid+1,r);
	pull(id, l, r);
	}

	void push(int i, int l, int r) {
	if(tag[i]) {
	seg[i] += tag[i] * (r - l + 1); // 更新區間 [l, r]
	if(l != r) { // 把標記往下推
	tag[cl(i)] += tag[i];
	tag[cr(i)] += tag[i];
	}
	tag[i] = 0; // 更新完區間後，把標記歸 0
	}
	}
	void update(int id,int l,int r,int ql, int qr, int v){
	push(id, l, r);
	...
	}
	int query(int id,int l,int r,int ql,int qr){
	push(id, l, r);
	...
	}

	void update(int id,int l,int r,int ql, int qr, int v){
	if(ql <= l && r <= qr){
	tag[id] += v;
	return;
	}
	int mid=(l+r)>>1;
	if(ql <= mid)
	update(cl(id),l,mid, ql, qr, v);
	if(qr > mid)
	update(cr(id),mid+1,r, ql, qr, v);
	pull(id, l, r); // 更新所有遍歷到的區間
	}

	void pull(int i, int l, int r) {
	int mid = (l+r)>>1;
	push(cl(i), l, mid);
	push(cr(i), mid + 1, r);
	seg[i] = seg[cl(i)] + seg[cr(i)];
	}

	int query(int i, int l, int r, int ql, int qr) {
	push(i, l, r);
	if(ql <= l && r <= qr) {
	return seg[i];
	}
	int mid = (l + r) / 2, ret = 0;
	if(ql <= mid)
	ret += query(cl(i), l, mid, ql, qr);
	if(qr > mid)
	ret += query(cr(i), mid + 1, r, ql, qr);
	return ret;
	}

線段樹(2)

區間更新區間詢問

使用單點修改線段樹

懶人標記 lazy tag

懶人標記 lazy tag

push 函數

pull 函數更新區間

pull 函數

更新範例程式碼

查詢

例題時間