# 線段樹1
by: hush
---
## 概念
----
線段樹(segment/interval tree)，是一種平衡二元樹，可支援**連續區間型的可分治操作**
----
### 適用問題
- 區間總和查詢
- 區間極值查詢
- 區間加值/改值
- 區間最大連續和
- 區間開根號
- 其他具有可分治性的區間問題
---
## 架構
----
示意圖
----
- 一棵二元樹：每個節點都對應一個區間
- 根節點對應總區間
- 左子節點對應左半區間，右子節點亦同
- 葉節點區間長度為1
- 每個節點通常存：當前區間的答案(、合併答案的資訊)
----
實作上通常會用陣列儲存線段樹，$a[1]$為根節點，$a[i]的左子節點為a[i\times 2]$，$右子節點為a[i\times 2+1]$這樣只需要開$a[4\times N]$就夠了($N$為總區間長度)
----
示意圖
---
## 範例1
----
接下來會以RMQ(區間最大值)舉例，會有一個初始陣列$a[n]$ ($n\le 10^5$)，接下來會有$q$ ($q\le 10^5$)筆操作，可能是把$a[i]$的值修改成$x$或詢問$a[l]$~$a[r]$的最大值
實作上我習慣seg陣列為1-base，區間為左閉右開
----
### 建樹函式
----
```cpp=1
constexpr int MAXN=100005;
int seg[MAXN<<2],a[MAXN]; //a<<2 == a*4
void build(int cur,int l,int r) //[l,r)
{
```
- seg存該節點(區間)的最大值，a為初始陣列
- cur為l~r區間在seg[]的索引(每個cur唯一對應一個區間)
----
```cpp=4
void build(int cur,int l,int r) //[l,r)
{
if (l+1==r) //leaf node
{
seg[cur]=a[l]; //唯一的元素就是最大值
return;
}
int mid=(l+r)>>1;
build(cur*2,l,mid); //cur*2為左節點
build(cur*2+1,mid,r); //cur*2+1為右節點
seg[cur]=max(seg[cur*2],seg[cur*2+1]);
}
```
----
時間複雜度：跑過所有$4n$個節點所以$O(n)$
----
### 修改函式
----
```cpp=18
void update(int cur,int l,int r,int i,int x)
{
```
- i是要修改的位置，x是修改的值
----
```cpp=18
void update(int cur,int l,int r,int i,int x)
{
if (l+1==r) //此時l==i
{
seg[cur]=x;
return;
}
int mid=(l+r)>>1;
if (i<mid) update(cur*2,l,mid,i,x); //i在左區間
else update(cur*2+1,mid,r,i,x); //i在右區間
seg[cur]=max(seg[cur*2],seg[cur*2+1]);
}
```
----
時間複雜度：一個level只拜訪一個節點
總共$\log(n)$個level所以$O(\log n)$
----
### 查詢函式
----
```cpp=32
int query(int cur,int l,int r,int ql,int qr)
{
```
- $ql, qr$代表詢問的區間，我習慣$[ql,qr)$
----
```cpp=32
int query(int cur,int l,int r,int ql,int qr)
{
if (r<=ql || l>=qr) return -1e18;//當前區間不在詢問區間內
if (ql<=l && r<=qr) return seg[cur]; //當前區間完全在詢問區間內
int mid=(l+r)>>1;
return max(query(cur*2,l,mid,ql,qr),query(cur*2+1,mid,r,ql,qr));
}
```
----
時間複雜度：$O(\log n)$有點難解釋
----
```cpp=41
signed main()
{
int n,q; cin >> n >> q;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n+1); //1-base, [l,r)
while (q--)
{
int op; cin >> op >> ;
if (op==1)
{
int i,x; cin >> i >> x;
update(1,1,n+1,i,x);
}
else
{
int ql,qr; cin >> ql >> qr;
cout << query(1,1,n+1,ql,qr+1) << endl; //[ql,qr)
}
}
}
```
----
- [範例題目連結](https://cses.fi/problemset/task/1649/)
- [CSDC408(我出的類題)](https://csdcojweb1.xi11.cc/problem/408)
---
## 範例2
----
給一個$n$個整數的陣列，處理$q$筆以下兩種操作：
1. 將位置$k$的值更新為$u$
2. 查詢區間$[a,b]$中所有值的總和
----
```cpp=1
constexpr int MAXN=100005;
int seg[MAXN<<2],a[MAXN]; //seg為區間總和
void build(int cur,int l,int r) //[l,r)
{
if (l+1==r) //leaf node
{
seg[cur]=a[l]; //唯一的元素就是加總
return;
}
int mid=(l+r)>>1;
build(cur*2,l,mid); //cur*2為左節點
build(cur*2+1,mid,r); //cur*2+1為右節點
seg[cur]=seg[cur*2]+seg[cur*2+1];
}
void update(int cur,int l,int r,int i,int x)
{
if (l+1==r) //此時l==i
{
seg[cur]=x;
return;
}
int mid=(l+r)>>1;
if (i<mid) update(cur*2,l,mid,i,x); //i在左區間
else update(cur*2+1,mid,r,i,x); //i在右區間
seg[cur]=seg[cur*2]+seg[cur*2+1];
}
int query(int cur,int l,int r,int ql,int qr)
{
if (r<=ql || l>=qr) return 0;
if (ql<=l && r<=qr) return seg[cur];
int mid=(l+r)>>1;
return query(cur*2,l,mid,ql,qr)+query(cur*2+1,mid,r,ql,qr);
}
signed main()
{
int n,q; cin >> n >> q;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n+1); //1-base, [l,r)
while (q--)
{
int op; cin >> op >> ;
if (op==1)
{
int i,x; cin >> i >> x;
update(1,1,n+1,i,x);
}
else
{
int ql,qr; cin >> ql >> qr;
cout << query(1,1,n+1,ql,qr+1) << endl; //[ql,qr)
}
}
}
```
----
- [範例題目連結](https://cses.fi/problemset/task/1648)
- [zj_d799(需要腦洞大開)](https://zerojudge.tw/ShowProblem?problemid=d799)
---
## 變化題
----
1.區間最早值
- 給一個$n$個整數的陣列，處理$q$筆詢問：
對於詢問值$x$，找出第一個$\ge x$個值的位置，並把該位置減去$x$後繼續下一次詢問
- 技巧：在線段樹上二分搜
----
方法：
- 一個維護區間最大值的線段樹(RMQ)
- 詢問時若左半區間最大值$\ge x$則答案在左邊，否則在右邊
- 遞迴直到葉節點
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
using namespace std;
int seg[(200000<<2)+5],ans=0;
void update(int cur,int l,int r,int i,int x) //add
{
if (l+1==r)
{
seg[cur]+=x;
return;
}
if (i<mid) update(lc,l,mid,i,x);
else update(rc,mid,r,i,x);
seg[cur]=max(seg[lc],seg[rc]);
}
void query(int cur,int l,int r,int x)
{
if (seg[cur]<x) return;
if (l+1==r)
{
ans=l;
return;
}
query(lc,l,mid,x);
if (!ans) query(rc,mid,r,x);
}
signed main()
{
//colinorz;
int n,m; cin >> n >> m;
for (int i=1;i<=n;i++)
{
int h; cin >> h; update(1,1,n+1,i,h);
}
for (;m--; ans=0)
{
int r; cin >> r;
query(1,1,n+1,r);
cout << ans << " \n"[m==0];
if (ans) update(1,1,n+1,ans,-r);
}
}
```
----
[範例題目連結(CSES)](https://cses.fi/problemset/task/1143/)
[範例題目連結(CF)](https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/C)
----
2.區間最大差
- 單點修改，詢問區間內任兩值的差最大可以是多少
- 方法：同時維護區間最大及最小值，詢問時相減及為答案
----
3.區間最大順向差
- 單點修改，詢問區間內任兩值後面減前面最大可以是多少
- 方法：同時維護區間最小值、最大值及答案(最大順向差)，詢問時答案是$\max(左區間答案,右區間答案,右最大-左最小)$
----
4.區間最大連續和
- 沒有修改，多筆詢問
- 方法1：區間和$=$前綴和順向差，所以答案就是前綴和陣列的區間最大順向差
- 方法2：維護最大前綴和、最大後綴和、區間和及答案(最大連續和)，詢問時答案是
$\max(左區間答案,右區間答案,左後綴+右前綴)$
---
## 練習題
----
- [CSES2206](https://cses.fi/problemset/task/2206)
- [CSES1561](https://cses.fi/problemset/task/1651/)
- [zj_f986(d799的進階)](https://zerojudge.tw/ShowProblem?problemid=f986)
----
- CSES2206題解：
此題為RMQ類題，維護$p_a+a$和$p_a-a$的區間最小值，答案就是$p_a+a-b,a\ge b$最小值和$p_a-a+b,a\le b$最小值取最小值
----
CSES2206 AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
using namespace std;
int seg[5][(200000<<2)+5]; //seg[0]->pa+a,seg[1]->pa-a
void update(int tr,int cur,int l,int r,int i,int x)
{
if (l+1==r)
{
seg[tr][cur]=(tr?-i:i)+x;
return;
}
if (i<mid) update(tr,lc,l,mid,i,x);
else update(tr,rc,mid,r,i,x);
seg[tr][cur]=min(seg[tr][lc],seg[tr][rc]);
}
int query(int tr,int cur,int l,int r,int ql,int qr)
{
if (qr<=l || r<=ql) return 1e9;
if (ql<=l && r<=qr) return seg[tr][cur];
return min(query(tr,lc,l,mid,ql,qr),query(tr,rc,mid,r,ql,qr));
}
signed main()
{
//colinorz;
int n,q; cin >> n >> q;
for (int i=1;i<=n;i++)
{
int p; cin >> p;
update(0,1,1,n+1,i,p); update(1,1,1,n+1,i,p);
}
while (q--)
{
int op,k,x;
if (cin>>op>>k && op==1)
{
cin >> x;
update(0,1,1,n+1,k,x); update(1,1,1,n+1,k,x);
}
else cout << min(query(0,1,1,n+1,k,n+1)-k,
query(1,1,1,n+1,1,k+1)+k) << endl;
}
}
```
----
- CSES1561題解：
差分序列的前綴和$=$原序列，維護差分序列$d$的前綴和，$[l,r]$都加$x$就是$d[l]+x,d[r+1]-x$
前綴和可以用區間和維護或是用[BIT](https://cp.wiwiho.me/fenwick-tree/)(常數佳)
----
CSES1561 AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
using namespace std;
int seg[(200000<<2)+5]={}; //seg[i]->d[i]
void update(int cur,int l,int r,int i,int x)
{
if (l+1==r)
{
seg[cur]+=x;
return;
}
if (i<mid) update(lc,l,mid,i,x);
else update(rc,mid,r,i,x);
seg[cur]=seg[lc]+seg[rc];
}
int query(int cur,int l,int r,int ql,int qr)
{
if (r<=ql || l>=qr) return 0;
if (ql<=l && r<=qr) return seg[cur];
return query(lc,l,mid,ql,qr)+query(rc,mid,r,ql,qr);
}
signed main()
{
//colinorz;
int n,q,lst=0,a; cin >> n >> q;
for (int i=1;i<=n;i++,lst=a)
{
cin >> a;
update(1,1,n+2,i,a-lst); //n+2避免qr+1溢位
}
while (q--)
{
int op; cin >> op;
if (op==1)
{
int ql,qr,x; cin >> ql >> qr >> x;
update(1,1,n+2,ql,x); update(1,1,n+2,qr+1,-x);
}
else
{
int i; cin >> i;
cout << query(1,1,n+2,1,i+1) << endl;
}
}
}
```
----
----
- zj_f986題解：
$L,R$為修改的部分，$D(x)$代表位置$x$前綴和的變化量，整理之後會變二次多項式，分別維護三個項的係數即可
$2D(x) =\begin{cases}
0, & \text{if } x < L \\
(x - L + 1)(x - L + 2), & \text{if } L \le x \le R \\
(R - L + 1)(R - L + 2), & \text{if } x > R
\end{cases}$
----
f986 AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define lc cur<<1
#define rc cur<<1|1
#define mid (l+r)>>1
using namespace std;
int a[200005]={};
int seg[5][(200000<<2)+5]={}; //seg[0]->a, seg[1]->b, seg[2]->c
void build(int cur,int l,int r)
{
if (l+1==r)
{
seg[2][cur]=a[l]<<1;
return;
}
build(lc,l,mid); build(rc,mid,r);
seg[2][cur]=seg[2][lc]+seg[2][rc];
}
void update(int tr,int cur,int l,int r,int i,int x)
{
if (l+1==r)
{
seg[tr][cur]+=x;
return;
}
if (i<mid) update(tr,lc,l,mid,i,x);
else update(tr,rc,mid,r,i,x);
seg[tr][cur]=seg[tr][lc]+seg[tr][rc];
}
int query(int tr,int cur,int l,int r,int ql,int qr)
{
if (qr<=l || ql>=r) return 0;
if (ql<=l && r<=qr) return seg[tr][cur];
return query(tr,lc,l,mid,ql,qr)+query(tr,rc,mid,r,ql,qr);
}
inline int pre(int n,int i)
{
return i*i*query(0,1,1,n+1,1,i+1)+i*query(1,1,1,n+1,1,i+1)+query(2,1,1,n+1,1,i+1);
}
signed main()
{
int n,q; cin >> n >> q;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n+1);
while (q--)
{
int c,ql,qr;
if (cin>>c>>ql>>qr && c==1)
{
/*
if (x<R) 2d(x)=(x-L+1)*(x-L+2)=x^2+ (-2L+3)x+ (L-2)*(L-1)
if (x>=R) 2d(x)=(R-L+1)*(R-L+2)
*/
update(0,1,1,n+1,ql,1); update(0,1,1,n+1,qr,-1);
update(1,1,1,n+1,ql,3-2*ql); update(1,1,1,n+1,qr,2*ql-3);
update(2,1,1,n+1,ql,(ql-2)*(ql-1)); update(2,1,1,n+1,qr,(ql-2)*(1-ql));
update(2,1,1,n+1,qr,(qr-ql+1)*(qr-ql+2)); //x>=qr
}
else cout << ((pre(n,qr)-pre(n,ql-1))>>1) << endl;
}
}
```
---
# 謝謝大家
{"description":"by: hush","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":12986,\"del\":2358}]","title":"線段樹1"}