# 線段樹 總論
[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的數的位置
* 也就是樹上二分
* 區間修改
* 小於<=x的元素個數，有這些做法：
* wavelet tree (不是線段樹)
* merge-sort-tree (特化的線段樹)
* BIT之樹套樹
* Mo's algorithm + sqrt decomposition
* 多項式修改
* 包含了設定，加總
總之，可以把線段數想像成或是核心，我們可以隨需求安裝上不同的插件（函數）。
比方說下面是一個最基礎的線段樹，僅支援範圍查詢：
```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`？
你不妨可以做做看
或是看[這個解答](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]}); // 特別是這一行
}
```
這就是原因。
:::info
可以想一下，在做數學歸納法的時候，有時會遇到想證明的東西無法從過去的東西推出來的情況。
這時候我們就要自己設計每個狀態有哪些命題為真。
像是
就用了五個命題。
好處就在於，條件多了，有興趣的命題就變得好證，但不好就在於
你要把多的這些不感興趣的條件給證了，才能給下個狀態用。
在這邊，也是一樣的意思。
意思就是，注意到數學歸納法跟遞回的密不可分的關西。
:::
---
#### 為什麼還需要 `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 ac code
```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)這提難題為例（題解來自影片），
現在我們要要求區間不能有任何的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';
}
}
```
:::
## 動態開點及主席樹（Persistent Segment Tree）
## w/ Line sweep
## 各種變形
Sign in with Wallet
Connect another wallet