---
# System prepended metadata

title: 線段樹 壹之型
tags: [algorithm]

---

# 線段樹 壹之型

介紹線段樹最基本的形式。

[toc]

## 線段樹原理與Code

本篇是根據[YT REF](https://www.youtube.com/watch?v=Teu-rb4uVVM)做成的筆記

Segment tree supports monoid(半群) operation. Especially fast for those operation that combines efficiently. E.g, if we know $sum(a,b]$ and $sum(b,c]$, then $sum(a,c]$ can be calculated $O(1)$.
However, if we know the mode(眾數) for the left and the mode for the right, it is difficult to know the mode for the whole. Such a query is then an example a segment tree can't handle.

:::info
見 http://hzwer.com/8053.html 之 分块入门 9 by hzwer
> 给出一个长为n的数列，以及n个操作，操作涉及询问区间的最小众数。
这是一道经典难题，其实可以支持修改操作...
:::

We use `int t[]`, 1-indexed to store values. For node `i`, the left child is `2*i`, and right child is `2*i+1`. 
:::info
This way of storage is also used in implementation of a heap.
:::

線段樹已經萬用到是一種思維概念或是程式範式，多年來在各路大神的澆灌下，這棵樹上已經開枝散葉出許多瘋狂的技巧，延伸之概念可說是子孫繁多。
以下列舉之：
* 樹套樹 (for higher dimension)
* 可持久化
* 動態開點樹
* 區間查詢
    * 極值
    * 總和
    * gcd/lcm
    * 各類位運算
    * 第一個大於x的數的位置 (也就是樹上二分)
    * maximum sum subarray 查詢
* 區間修改
    * 小於<=x的元素個數，有這些做法：
        * wavelet tree (不是線段樹)
        * merge-sort-tree (特化的線段樹)
        * BIT之樹套樹
        * Mo's algorithm + sqrt decomposition
    * 多項式修改
        * 包含了設定，加總
* 勢能分析變形
* Li Chao Tree 
* Segment tree beats

總之，可以把線段樹想像成或是核心，我們可以隨需求安裝上不同的插件（函數）。

比方說下面是一個最基礎的線段樹，僅支援範圍查詢：
```cpp=
struct segtree {
    ll arr[maxn], ll t[maxn<<2];
    build(int l,int r,int i) {
        if (l==r) {
            t[l] = arr[l];
            return;
        }
        int mid = (l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        t[i] = t[i<<1] + t[i<<1|1];
    }
    ll query(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) return t[i];
        ll ans = 0;
        int mid = (l+r)>>1;
        if (jl <= mid) ans += query(jl,jr,l,mid,i<<1);
        if (jr > mid) ans += query(jl,jr,mid+1,r,i<<1|1);
        return ans;
    }
```
可以想成
1. 安裝了`build`插件，使支援$O(n)$建樹
2. 安裝了`query`插件，使支援$O(\log n)$區間總和查詢


可以繼續安裝插件，使其具有更多功能，比方說，來一個單點累加的方法：
```cpp=21
    void point_add(int idx,int val,int l,int r,int i) {
        t[i] += val*(r-l+1);
        if (l==r) return;
        int mid = (l+r)>>1;
        if (jl <= mid) point_add(idx,val,l,mid,i<<1);
        if (jr > mid) point_add(idx,val,mid+1,r,i<<1|1);
        t[i] = t[i<<1] + t[i<<1|1];
    }
};
```
目前，我們得到了與BIT完全一樣的功能。

此時碼量來到29行。但對於有志之士來說，既然訴諸了線段樹，豈會滿足於點累加？肯定還要來點區間累加才對。

如果套上lazy propagation等模板，代碼便來到58行。
:::spoiler
```cpp=
ll arr[200001], t[200001<<2], lazy[200001<<2];
struct segtree {
    int n;
    segtree(int n): n(n) {
        build(0,n-1,1);
    }
    void apply(ll val,int l,int r,int i) {
        t[i] += (r-l+1)*val;
        lazy[i] += val;
    }
    void down(int l,int r,int i) {
        if (!lazy[i]) return;
        int mid = (l+r)>>1;
        apply(lazy[i],l,mid,i<<1);
        apply(lazy[i],mid+1,r,i<<1|1);
        lazy[i] = 0;
    }
    void up(int i) {
        t[i] = t[i<<1]+t[i<<1|1];
    }
    void build(int l,int r,int i) {
        if (l==r) {
            t[i] = arr[l];
            return;
        }
        int mid = (l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        up(i);
    }
    ll query(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) return t[i];
        ll ans = 0;
        int mid = (l+r)>>1;
        down(l,r,i);
        if (jl <= mid) ans+=query(jl,jr,l,mid,i<<1);
        if (jr > mid) ans+=query(jl,jr,mid+1,r,i<<1|1);
        up(i);
        return ans;
    }
    ll query(int jl,int jr) {
        return query(jl,jr,0,n-1,1);
    }
    void add(int jl,int jr,ll val,int l,int r,int i) {
        if (jl <= l && r <= jr) {
            apply(val,l,r,i);
            return;
        }
        int mid = (l+r)>>1;
        down(l,r,i);
        if (jl <= mid) add(jl,jr,val,l,mid,i<<1);
        if (jr > mid) add(jl,jr,val,mid+1,r,i<<1|1);
        up(i);
    }
    void add(int jl,int jr,ll val) {
        add(jl,jr,val,0,n-1,1);
    }
};
```
:::
我們應該釐清這些新變數的意義。
`lazy`： `lazy[i]`如果有值，表示 `t[i]` 的節點已經按照要求做完累加了，但是他的兒子還沒有。
`down`： 因為兒子的`t[i]`還沒有做累加，所以要下發給左右。這在查詢及修改時都要做。
`up`：左右修改完後，要合併給父節點。其實只在修改時要做（也就是38行可以省去的意思），因為查詢除了由過往`lazy`帶來的左右兒子的修改外，沒有別的修改，而關於這個修改所必須做的修正早就完成了。

此時碼量來到58行。但對於有志之士來說，既然訴諸了線段樹，豈會滿足於區間累加？肯定還要來點區間設定才對。

為了顧及兩種操作的順序及正確性，代碼便來到87行。

:::spoiler

```cpp=
#define maxn 200001
int arr[maxn];
ll unset = 1145141919810;
ll t[maxn<<2], slazy[maxn<<2], alazy[maxn<<2];
struct segtree {
	int n;
	segtree(int n): n(n) {
		fill(alazy,alazy+(n<<2),0);
		fill(slazy,slazy+(n<<2),unset);
		build(0,n-1,1);
	}
	void build(int l,int r,int i) {
		if (l==r) {
			t[i] = arr[l];
			return;
		}
		int mid = (l+r)>>1;
		build(l,mid,i<<1);
		build(mid+1,r,i<<1|1);
		up(i);
	}
	void down(int l,int r,int i) {
		int mid = (l+r)>>1;
		if (slazy[i] != unset) {
			sapply(slazy[i],l,mid,i<<1);
			sapply(slazy[i],mid+1,r,i<<1|1);
			slazy[i] = unset;
		}
		if (alazy[i]) {
			aapply(alazy[i],l,mid,i<<1);
			aapply(alazy[i],mid+1,r,i<<1|1);
			alazy[i] = 0;
		}
	}
	void up(int i) {
		t[i] = t[i<<1] + t[i<<1|1];
	}
	void sapply(ll v,int l,int r,int i) {
		alazy[i] = 0;
		t[i] = (r-l+1)*v;
		slazy[i] = v;
	}
	void aapply(ll v,int l,int r,int i) {
		t[i] += (r-l+1)*v;
		alazy[i] += v;
	}
	ll query(int jl,int jr,int l,int r,int i) {
		if (jl <= l && r <= jr) return t[i];
		ll ans = 0;
		int mid = (l+r)>>1;
		down(l,r,i);
		if (jl <= mid) ans += query(jl,jr,l,mid,i<<1);
		if (jr > mid) ans += query(jl,jr,mid+1,r,i<<1|1);
		return ans;
	}
	ll query(int jl,int jr) {
		return query(jl,jr,0,n-1,1);
	}
	void add(int jl,int jr,int v,int l,int r,int i) {
		if (jl <= l && r <= jr) {
			aapply(v,l,r,i);
			return;
		}
		int mid = (l+r)>>1;
		down(l,r,i);
		if (jl <= mid) add(jl,jr,v,l,mid,i<<1);
		if (jr > mid) add(jl,jr,v,mid+1,r,i<<1|1);
		up(i);
	}
	void add(int jl,int jr,int v) {
		add(jl,jr,v,0,n-1,1);
	}
	void set(int jl,int jr,int v,int l,int r,int i) {
		if (jl <= l && r <= jr) {
			sapply(v,l,r,i);
			return;
		}
		int mid = (l+r)>>1;
		down(l,r,i);
		if (jl <= mid) set(jl,jr,v,l,mid,i<<1);
		if (jr > mid) set(jl,jr,v,mid+1,r,i<<1|1);
		up(i);
	}
	void set(int jl,int jr,int v) {
		set(jl,jr,v,0,n-1,1);
	}
};
```

:::

:::info

事實上，很多都是重複的代碼跟邏輯。花頂多一個禮拜的時間，不用死背就可以學得得心應手。

:::

### 一種優雅的寫法： $f-$修改
> 以下的內容是筆者做夢想到的，但應該有人早就有跟我一樣的想法並發到網上了但隨便啦

上面的方法，汲汲營營的把`lazy`, `apply`分成兩種，一種照顧設定，一種照顧加值，
我們就要費很多腦細胞處理好他們的先後順序關西（因為設定操作會覆蓋掉加值操作），寫成了也不好解釋。

我們不妨處理好
> 將區間[l,r]的所有數字根據函數 `f` 做變換。

亦即，本來是 $$a_0, \dots, a_l, \dots, a_r, \dots, a_{n-1}$$
現在是 $$a_0, \dots, f(a_l), \dots, f(a_r), \dots, a_{n-1}$$
如果可以處理好這種query，並且當$f(x) = ax+b$ 也就是是一個 affine map 的時候，不就同時處理好了

1. 區間設定
2. 區間加值，甚至是
3. 區間乘

等操作了嗎？

:::spoiler
```cpp=
using ll = long long;
struct poly {
    ll a, b;
};
bool operator==(const poly& l,const poly& r) {
    return l.a == r.a && l.b == r.b;
}
poly id{1,0};
#define maxn 200001
int arr[maxn];
ll t[maxn<<2];
poly lz[maxn<<2];
struct segtree {
    int n;
    segtree(int n): n(n) {
        fill(lz,lz+(n<<2),id);
        build(0,n-1,1);
    }
    void build(int l,int r,int i) {
        if (l==r) {
            t[i] = arr[l];
            return;
        }
        int mid = (l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        up(i);
    }
    void down(int l,int r,int i) {
        int mid = (l+r)>>1;
        if (lz[i] != id) {
            apply(lz[i],l,mid,i<<1);
            apply(lz[i],mid+1,r,i<<1|1);
            lz[i] = id;
        }
    }
    void up(int i) {
        t[i] = t[i<<1] + t[i<<1|1];
    }
    void apply(poly v,int l,int r,int i) {
        t[i] = v.a*t[i] + v.b*(r-l+1);
        lz[i] = poly{v.a*lz[i].a,v.a*lz[i].b + v.b};
    }
    ll query(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) return t[i];
        ll ans = 0;
        int mid = (l+r)>>1;
        down(l,r,i);
        if (jl <= mid) ans += query(jl,jr,l,mid,i<<1);
        if (jr > mid) ans += query(jl,jr,mid+1,r,i<<1|1);
        return ans;
    }
    ll query(int jl,int jr) {
        return query(jl,jr,0,n-1,1);
    }
    void modify(ll a,ll b,int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) {
            apply(poly{a,b},l,r,i);
            return;
        }
        int mid = (l+r)>>1;
        down(l,r,i);
        if (jl <= mid) modify(a,b,jl,jr,l,mid,i<<1);
        if (jr > mid) modify(a,b,jl,jr,mid+1,r,i<<1|1);
        up(i);
    }
    void modify(ll a,ll b,int jl,int jr) {
        modify(a,b,jl,jr,0,n-1,1);
    }
};

```
:::

原來的寫法，我們要謹慎處理他們的先後順序。現在，`先乘除後加減`自動幫我們做好了這部分。
注意程式碼更少但支援的操作反而更多！

$f$還可以是別的多項式或是有理式，他們的懶標記累加起來都比較直觀（雖然麻煩）。
更可以是max，min，clamp。但是需要特別處理技巧，見
[A simple introduction to "Segment tree beats"](https://codeforces.com/blog/entry/57319)

## 特別訊息維護之區間合併

為了回答特別的query，我們有必要特別練習設計狀態的方式，
使得區間容易合併出大答案。

現在，以leetcode的 [53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/description/) 為例。

### 使用的線段樹介紹

Kadane's alg. 也許優雅，卻不夠潮。現在，我們要用同樣線性時間的線段樹手法解開這題。

為此，我們要構建一棵支援「單點修改」和「區間查詢」的線段樹。在一次查詢中，我們得同時回答：

* 從 `jl` 開始的最大前綴和  
* 以 `jr` 結尾的最大後綴和  
* 區間 `[jl, jr]` 的最大子陣列和  
* 區間 `[jl, jr]` 的總和  

一旦構建好這棵線段樹，這題就變得相當簡單。

甚至（雖然題目沒問），我們還能$O(\log n)$改值。配上懶標更能範圍改。

`build` 方法和 `set` 方法都是老生常談了  

困難的部分是如何設計一個`query`，能從左右子區間的資訊構造出父節點的資訊，也就是 `up` 與 `q` 的功能。

---

### `up` 與 `q` 方法

圈內人士都知道，`up`（有些人也叫 `pull`）是用來把左右子節點的資訊合併成父節點的資訊。

我們在樹上儲存：
```cpp
// sum : 區間總和
// pre : 最大前綴和
// suf : 最大後綴和
// c   : 最大子陣列和
ll sum[maxn<<2], pre[maxn<<2], suf[maxn<<2], c[maxn<<2];
```

這些資訊都是為了計算 `c`（最大子陣列和）所必需的。  

為什麼需要 `pre` 和 `suf`？

不妨可以做做看
![image](https://hackmd.io/_uploads/HJ7c5pOFeg.png)
或是看[這個解答](https://leetcode.com/problems/maximum-subarray/solutions/1595195/c-python-7-simple-solutions-w-explanation-brute-force-dp-kadane-divide-conquer/)
就可以略知一二，尤其是第七個解，

```cpp
void up(int l,int r,int i) {
    int il = i<<1, ir = i<<1|1;

    sum[i] = sum[il] + sum[ir];

    pre[i] = max(pre[il], sum[il] + pre[ir]);
    suf[i] = max(suf[ir], suf[il] + sum[ir]);
    c[i] = max({c[il], c[ir], suf[il] + pre[ir]}); // 特別是這一行
}
```

也許就能看出原因。

可以想一下，在做數學歸納法的時候，有時會遇到想證明的東西無法從過去的東西推出來的情況。
這時候我們就要自己設計每個狀態有哪些命題為真。
像是 Rudin 的這個定理
![image](https://hackmd.io/_uploads/B14PnpuKex.png)
就用了五個命題當遞推條件。
好處就在於，條件多了，有興趣的命題就變得好證，但不好就在於
你要把多的這些不感興趣的條件給證了，才能給下個狀態用。

在這邊，也是一樣的意思。
意思就是，注意到 mathematical induction 跟 recursion 的密不可分的關係。
問題 「為什麼上面的定理在做歸納法時要假設跟我們想要的東西差很多的條件？」跟問題「為什麼我們只要查連續長度而已，卻又要搞 `pre` 跟 `suf`？」本質上是一樣的。

#### 為什麼還需要 `sum`？

不能直接寫成這樣嗎？

```cpp
void up(int l,int r,int i) {
    int il = i<<1, ir = i<<1|1;
    pre[i] = max(pre[il], pre[il] + pre[ir]);
    suf[i] = max(suf[ir], suf[il] + suf[ir]);
    c[i] = max({c[il], c[ir], suf[il] + pre[ir]});
}
```

答案：不行。考慮以下例子：  
`1, -114514, -1919, 1, 0, 0`  

在 `[0,2]` 的最大前綴和是 1，在 `[3,5]` 的最大前綴和也是 1，但整體 `[0,5]` 的最大前綴和不是 1+1，如果這樣計算就錯了。  

簡單說，我們不能只拿左邊的部分前綴和，然後跳過 `-114514`。  
我們需要 `sum` 來判斷是否應該把整個左區間都包含進來。  

這就是為什麼它和純粹的 Divide & Conquer 解法不同，在這裡 `sum` 是必須的。  

類似地，`q` 方法也是基於同樣的想法：它回傳子區間的所有必要資訊，方便合併出父節點的結果。

---

#### TC

建樹需要 $O(n)$，因為 `up` 是 $O(1)$。  
查詢最大子陣列和則需要 $O(\log n)$。  

事實上，樹建好之後，答案就儲存在 `c[1]`，因此只要直接回傳 `c[1]`，查詢就變成 $O(1)$。  

所以整體：TC = SC = $O(n)$。

---

:::spoiler
```cpp
using ll = long long;
#define maxn 100001
int arr[maxn];

// sum : 區間總和
// pre : 最大前綴和
// suf : 最大後綴和
// c   : 最大子陣列和
ll sum[maxn<<2], pre[maxn<<2], suf[maxn<<2], c[maxn<<2];

struct segtree {
    int n;
    segtree(int n): n(n) {
        build(0, n-1, 1);
    }
    void up(int l,int r,int i) {
        int il = i<<1, ir = i<<1|1;

        sum[i] = sum[il] + sum[ir];

        pre[i] = max(pre[il], sum[il] + pre[ir]);
        suf[i] = max(suf[ir], suf[il] + sum[ir]);
        c[i] = max({c[il], c[ir], suf[il] + pre[ir]});
    }
    void build(int l,int r,int i) {
        if (l==r) {
            pre[i] = suf[i] = c[i] = arr[l];
            sum[i] = arr[l];
            return;
        }
        int mid = midpoint(l,r);
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        up(l,r,i);
    }
    void set(int idx,int v,int l,int r,int i) {
        if (l==r) {
            sum[i] = v;
            pre[i] = suf[i] = c[i] = v;
            return;
        }
        int mid = midpoint(l,r);
        if (idx <= mid) set(idx,v,l,mid,i<<1);
        else set(idx,v,mid+1,r,i<<1|1);
        up(l,r,i);
    }
    // 回傳 pre, suf, c, sum
    tuple<ll,ll,ll,ll> q(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) return {pre[i],suf[i],c[i],sum[i]};
        int mid = midpoint(l,r);
        if (jr<=mid) return q(jl,jr,l,mid,i<<1);
        if (jl>mid) return q(jl,jr,mid+1,r,i<<1|1);
        auto [prel,sufl,cl,sl] = q(jl,jr,l,mid,i<<1);
        auto [prer,sufr,cr,sr] = q(jl,jr,mid+1,r,i<<1|1);
        return {
            max(sl+prer,prel),
            max(sufr, sufl+sr),
            max({cl,cr,sufl+prer}),
            sl+sr
        };
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        for (int i=0;i<n;i++) arr[i] = nums[i];
        segtree seg(n);
        return get<2>(seg.q(0,n-1,0,n-1,1));
        // 第 3 個元素 (c) 是最大子陣列和
    }
};
```
:::

---

### 備註

潮就潮在，使用這個完全相同的線段樹，然後改一改 `main()`，可以直接 AC CSES 上的這四題：  

* [Prefix Sum Queries](https://cses.fi/problemset/task/2166)  
* [Range Interval Queries](https://cses.fi/problemset/task/3163)  
* [Subarray Sum Queries II](https://cses.fi/problemset/task/3226)  
* [Dynamic Range Sum Queries](https://cses.fi/problemset/task/1648)  

### 再做一題

以[P2572 [SCOI2010] 序列操作](https://www.luogu.com.cn/problem/P2572) (或者 [CSES / Bit Inversion](https://cses.fi/problemset/list/) 兩者根本是同一題)這提難題為例（題解來自影片），
現在我們要要求區間不能有任何的0，所以合併時要再考慮一下，並不是總是可以貪心。

不如直接看代碼

::: spoiler code
```cpp=
#include <bits/stdc++.h>
#define maxn 100002
using namespace std;

// orig
int arr[maxn];
// data
int sum[maxn<<2];
int pre0[maxn<<2], suf0[maxn<<2], c0[maxn<<2];
int pre1[maxn<<2], suf1[maxn<<2], c1[maxn<<2];
// lazy
int set_to[maxn<<2], unset = -1;
bool flip[maxn<<2];

struct segtree {
    int n;
    segtree(int n): n(n) {
        // 注意1 : 直接sizeof(set_to) 全部清零。
        // 這點小時間不足掛齒
        memset(set_to,unset,sizeof(set_to));
        memset(flip,0,sizeof(flip));
        build(0,n-1,1);
    }
    void build(int l,int r,int i) { // 
        if (l==r) {
            sum[i] = arr[l];
            pre0[i] = suf0[i] = c0[i] = (arr[l]==0);
            pre1[i] = suf1[i] = c1[i] = (arr[l]==1);
            return;
        }
        int mid = midpoint(l,r);
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        up(l,r,i);
    }
    void down(int l,int r,int i) {
        int mid = midpoint(l,r);
        // 注意2 : 先處理set再處理flip
        if (set_to[i] != unset) {
            apply_set(set_to[i],l,mid,i<<1);
            apply_set(set_to[i],mid+1,r,i<<1|1);
            set_to[i] = unset;
        }
        if (flip[i]) {
            apply_flip(l,mid,i<<1);
            apply_flip(mid+1,r,i<<1|1);
            flip[i] = false;
        }
    }
    // 注意4 : first encounterence of 三個變數的up方法
    void up(int l,int r,int i) {
        sum[i] = sum[i<<1] + sum[i<<1|1];
        int n = (r-l+1), mid = midpoint(l,r);
        // 注意5 : 用變數所以你不會眼花撩亂
        int nl = mid-l+1, nr = r-mid;
        int lv = i<<1, rv = i<<1|1;
    
        // 注意6 : 可以換成 pre0[i] = (c0[lv] < nl)?pre0[lv]:nl+pre0[rv];
        // 但這種寫法較雅觀
        pre0[i] = (c0[lv] < nl)?pre0[lv]:pre0[lv]+pre0[rv];
        suf0[i] = (c0[rv] < nr)?suf0[rv]:suf0[lv]+suf0[rv];
        c0[i] = max({c0[lv],c0[rv],suf0[lv]+pre0[rv]});

        pre1[i] = (c1[lv] < nl)?pre1[lv]:pre1[lv]+pre1[rv];
        suf1[i] = (c1[rv] < nr)?suf1[rv]:suf1[lv]+suf1[rv];
        c1[i] = max({c1[lv],c1[rv],suf1[lv]+pre1[rv]});
    }
    void apply_set(int v,int l,int r,int i) {
        sum[i] = (v==1?r-l+1:0);
        pre0[i] = suf0[i] = c0[i] = (v==0?r-l+1:0);
        pre1[i] = suf1[i] = c1[i] = (v==1?r-l+1:0);
        set_to[i] = v;
        flip[i] = false;
    }
    void apply_flip(int l,int r,int i) {
        sum[i] = (r-l+1)-sum[i];
        swap(pre0[i],pre1[i]), swap(suf0[i],suf1[i]), swap(c0[i],c1[i]);
        flip[i] = !flip[i];
        // 注意7 : 不用寫
        // if (set_to[i] != unset) set_to[i] ^= 1;
    }
    void set(int v,int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) {
            apply_set(v,l,r,i);
            return;
        }
        int mid = midpoint(l,r);
        down(l,r,i);
        if (jl <= mid) set(v,jl,jr,l,mid,i<<1);
        if (jr > mid) set(v,jl,jr,mid+1,r,i<<1|1);
        up(l,r,i);
    }
    void fl(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) {
            apply_flip(l,r,i);
            return;
        }
        int mid = midpoint(l,r);
        down(l,r,i);
        if (jl <= mid) fl(jl,jr,l,mid,i<<1);
        if (jr > mid) fl(jl,jr,mid+1,r,i<<1|1);
        up(l,r,i);
    }
    int qsum(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) return sum[i];
        int ans = 0, mid = midpoint(l,r);
        down(l,r,i);
        if (jl <= mid) ans += qsum(jl,jr,l,mid,i<<1);
        if (jr > mid) ans += qsum(jl,jr,mid+1,r,i<<1|1);
        // 注意8 : 不用 up 想想為啥
        return ans;
    }
    tuple<int,int,int> qc(int jl,int jr,int l,int r,int i) {
        if (jl <= l && r <= jr) return {pre1[i],suf1[i],c1[i]};
        int mid = midpoint(l,r);
        down(l,r,i);
        if (jr <= mid) return qc(jl,jr,l,mid,i<<1);
        if (jl > mid) return qc(jl,jr,mid+1,r,i<<1|1);

        auto [lpre1,lsuf1,lc1] = qc(jl,jr,l,mid,i<<1);
        auto [rpre1,rsuf1,rc1] = qc(jl,jr,mid+1,r,i<<1|1);

        // 注意9 : 為啥是 max, min?
        int nl = mid-max(l,jl)+1, nr = min(r,jr)-mid;
        return {
            (lc1 < nl)?lpre1:lpre1+rpre1,
            (rc1 < nr)?rsuf1:lsuf1+rsuf1,
            max({lc1,rc1,lsuf1+rpre1})
        };
    }
};

int main() {
    cin.tie(0), ios::sync_with_stdio(0);

    int n,m;
    cin >> n >> m;
    for (int i=0;i<n;i++) cin >> arr[i];
    segtree seg(n);
    for (int i=0;i<m;i++) {
        int t,l,r;
        cin >> t >> l >> r;
        if (t==0 || t==1) seg.set(t,l,r,0,n-1,1);
        else if (t==2) seg.fl(l,r,0,n-1,1);
        else if (t==3) cout << seg.qsum(l,r,0,n-1,1) << '\n';
        else cout << get<2>(seg.qc(l,r,0,n-1,1)) << '\n';
    }
}

```
:::

關於注意點九，一切的核心都是判斷 pre 跟 suf 的計算能不能從另一邊的區間拓展。
$[nl, mid]$ 的意義是左樹所管理的區間跟 $[jl,jr]$ 的並，同樣有
$[mid+1,nr]$ 的意義是右樹所管理的區間跟 $[jl,jr]$ 的並

比方說，如果左樹的最大連續 1 (aka `lc1`)的個數跟 $[nl, mid]$ 的長一樣，代表左樹全是 `1`，所以在計算 `pre` 時就可以延長。

這種做法思維量較多，另外一種等價但常數稍大的做法是同時維護左右區間的最小值，如果左右樹的最小值是 $1$ 代表該區間都是 $1$ 所以就很讚，讓 parent 的 pre/ suf 可以直接延長。因為本題只有 '0' 跟 '1'，最小值相當於 `boolean`, 而 `min` 操作可相當於 `&&`.

```cpp
// minimum, prefix contiguous 1, suffix contiguous 1, total contiguous 1
tuple<bool,int,int,int> query(int jl,int jr,int l,int r,int i) {
    if (jl <= l && r <= jr) return {m[i],pre[i],suf[i],tot[i]};
    int mid = midpoint(l,r);
    if (jr<=mid) return query(jl,jr,l,mid,i<<1);
    if (mid<jl) return query(jl,jr,mid+1,r,i<<1|1);
    auto [ml,prel,sufl,totl] = query(jl,jr,l,mid,i<<1);
    auto [mr,prer,sufr,totr] = query(jl,jr,mid+1,r,i<<1|1);
    return {
        ml && mr,
        ml ? totl + prer : prel,
        mr ? sufl + totr : sufr,
        max({totl, sufl + prer, totr})
    ;
}
```



