# 線段樹2
by:hush
---
## 懶惰標記(lazy tag)
----
- 先看一個問題：
給一個序列(長度$n\le 2\cdot 10^5$)，做$q\le 10^5$筆操作，對指定區間內的每個元素加某個數$x$或是詢問某區間的和
一個一個加肯定TLE！
----
並不是每個區間都需要算！哪些才需要算？
- Ans: 會用到的再算，因為詢問次數不會TLE，你只算問到的也不會
----
### 怎麼達成「只算需要的」？
- 用一種叫做「懶惰標記」（lazy tag）的技巧
- 想法：不是每次都真的去加值，而是記下「這個區間以後要加多少」
- 查詢或更新到更下面區間時，再把之前欠的值下傳下去(push)
----
### 懶惰標記的結構
- 每個節點都多記一個`tag`值，表示「這個區間每個值要多加多少」
- 當下推的時候，再把這些加到子節點上，更新子節點的 sum 值
- <span style="color:red">注意：該區間的tag只會影響子孫區間</span>
----
Code(前置部分)
```cpp=
struct node
{
int sum=0,tag=0;
} seg[500005<<2];
void addtag(int cur,int x,int len) //把區間加上懶標
{
seg[cur].sum+=x*len; //修改當前區間
seg[cur].tag+=x;
}
void push(int cur,int l,int mid,int r)
{ //把懶標打給兩個子節點
addtag(lc,seg[cur].tag,mid-l);
addtag(rc,seg[cur].tag,r-mid);
seg[cur].tag=0;
}
```
----
Code(修改函式)
```cpp=
void update(int cur,int l,int r,int ql,int qr,int x)
{
if (r<=ql || l>=qr) return;
if (ql<=l && r<=qr)
{
addtag(cur,x,r-l);
return;
}
if (seg[cur].tag!=0)
push(cur,l,mid,r); //更新子區間的值
update(lc,l,mid,ql,qr,x); update(rc,mid,r,ql,qr,x);
seg[cur].sum=seg[lc].sum+seg[rc].sum;
}
```
----
Code(詢問函式)
```cpp=
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].sum;
if (seg[cur].tag)
push(cur,l,mid,r); //更新子區間的值
return query(lc,l,mid,ql,qr)+query(rc,mid,r,ql,qr);
}
```
----
### 時間複雜度
每次修改或詢問都是$O(\log n)$的時間
----
### 例題1
- 題目([zj_d799](https://zerojudge.tw/ShowProblem?problemid=d799))：區間加值，區間求和
如果有時間可以看看底下不同做法
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#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;
struct node
{
int sum=0,tag=0;
} seg[500005<<2];
void addtag(int cur,int x,int len) //把區間加上懶標
{
seg[cur].sum+=x*len; //修改當前區間
seg[cur].tag+=x;
}
void push(int cur,int l,int mid,int r)
{ //把懶標打給兩個子節點
addtag(lc,seg[cur].tag,mid-l);
addtag(rc,seg[cur].tag,r-mid);
seg[cur].tag=0;
}
void update(int cur,int l,int r,int ql,int qr,int x)
{
if (r<=ql || l>=qr) return;
if (ql<=l && r<=qr)
{
addtag(cur,x,r-l);
return;
}
if (seg[cur].tag!=0)
push(cur,l,mid,r); //更新子區間的值
update(lc,l,mid,ql,qr,x); update(rc,mid,r,ql,qr,x);
seg[cur].sum=seg[lc].sum+seg[rc].sum;
}
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].sum;
if (seg[cur].tag)
push(cur,l,mid,r); //更新子區間的值
return query(lc,l,mid,ql,qr)+query(rc,mid,r,ql,qr);
}
signed main()
{
colinorz;
int n,q,v,ql,qr,x; cin >> n;
for (int i=0;i<n;i++)
{
cin >> x;
update(1,0,n,i,i+1,x);
}
cin >> q;
while (q--)
{
if (cin>>v>>ql>>qr && v==1)
{
cin >> x; update(1,0,n,ql-1,qr,x);
}
else cout << query(1,0,n,ql-1,qr) << endl;
}
}
```
---
## 修改順序
----
- 題目變難了：
長度為$n\le 2\cdot 10^5$的序列，處理以下操作：
1.將區間$[l,r]$中的每個值 **增加$x$**。
2.將區間$[l,r]$中的每個值 **變成$x$**。
3.計算區間$[l,r]$中所有值的 **總和**。
----
- 想法：我們需要兩個懶標，一個代表增加多少，一個代表修改成多少
- 問題：在`push`時要先 **修改** 區間值還是先 **增加** 區間值？
答：<span class="fragment">一般來說「先改再加」較好寫</span>
----
### 實作方法
- 加值時：直接在標記加值的tag上加值
- 改值時：先清空加值的tag，再修改改值的tag
- push時(順序不能變)：
1.若能改值則push改值的tag
2.若能加值則push加值的tag
----
Code(push函式)
```cpp=
struct node
{
int sum=0,tag1=0,tag2=0; //tag1->alt,tag2->add
} seg[(200000<<2)+5];
inline void addtag1(int cur,int l,int r,int x)
{
seg[cur].sum=x*(r-l),seg[cur].tag1=x;
seg[cur].tag2=0; //將加值設為0!!!
}
inline void addtag2(int cur,int l,int r,int x)
{
seg[cur].sum+=x*(r-l),seg[cur].tag2+=x;
}
void push(int cur,int l,int r)
{
if (seg[cur].tag1!=0) //tag1代表改值
{
addtag1(lc,l,mid,seg[cur].tag1);
addtag1(rc,mid,r,seg[cur].tag1);
seg[cur].tag1=0;
}
if (seg[cur].tag2!=0) //tag2代表加值
{
addtag1(lc,l,mid,seg[cur].tag2);
addtag1(rc,mid,r,seg[cur].tag2);
seg[cur].tag2=0;
}
}
```
----
### 例題2
- 題目([CSES1735](https://cses.fi/problemset/task/1735/))：區間加值、改值，區間求和
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#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;
struct node
{
int sum=0,tag1=0,tag2=0; //tag1->alt,tag2->add
} seg[(200000<<2)+5];
inline void addtag1(int cur,int l,int r,int x)
{
seg[cur].sum=x*(r-l),seg[cur].tag1=x,seg[cur].tag2=0;
}
inline void addtag2(int cur,int l,int r,int x)
{
seg[cur].sum+=x*(r-l),seg[cur].tag2+=x;
}
void push(int cur,int l,int r)
{
int &x1=seg[cur].tag1,&x2=seg[cur].tag2;
if (x1) addtag1(lc,l,mid,x1),addtag1(rc,mid,r,x1),x1=0;
if (x2) addtag2(lc,l,mid,x2),addtag2(rc,mid,r,x2),x2=0;
}
void alt(int cur,int l,int r,int ql,int qr,int x)
{
if (r<=ql || l>=qr) return;
if (ql<=l && r<=qr)
{
addtag1(cur,l,r,x);
return;
}
push(cur,l,r);
alt(lc,l,mid,ql,qr,x); alt(rc,mid,r,ql,qr,x);
seg[cur].sum=seg[lc].sum+seg[rc].sum;
}
void add(int cur,int l,int r,int ql,int qr,int x)
{
if (r<=ql || l>=qr) return;
if (ql<=l && r<=qr)
{
addtag2(cur,l,r,x);
return;
}
push(cur,l,r);
add(lc,l,mid,ql,qr,x); add(rc,mid,r,ql,qr,x);
seg[cur].sum=seg[lc].sum+seg[rc].sum;
}
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].sum;
push(cur,l,r);
return query(lc,l,mid,ql,qr)+query(rc,mid,r,ql,qr);
}
signed main()
{
colinorz;
int n,q; cin >> n >> q;
for (int i=1;i<=n;i++)
{
int a; cin >> a;
add(1,1,n+1,i,i+1,a);
}
while (q--)
{
int op,a,b,x;
if (cin>>op>>a>>b && 3==op) cout << query(1,1,n+1,a,b+1) << endl;
else if (cin>>x && 2==op) alt(1,1,n+1,a,b+1,x);
else add(1,1,n+1,a,b+1,x);
}
}
```
---
## 動態開點
----
- 當序列長度非常大（例如$n\le 10^9$），無法預先建立完整的線段樹。
- 解法：**動態開點**，僅在需要用到時才建立節點，節省空間。
----
### 動態開點的結構
開一個`struct`存當前節點(區間)的資訊，並利用指標指向兩個子節點
----
- 例題3([CSES1144](https://cses.fi/problemset/task/1144))：
給你一個序列(長度$n\le 2\cdot 10^5$)，序列值$\le 10^9$，處理兩種操作：
1.單點修改某個值。
2.查詢序列中有幾個值在區間$[l,r]$內。
----
- 解法：
將$[1,10^9]$視為一個線段，某個點為0代表沒人，1則是有人
題目可轉換為求$[l,r]$有幾個1（區間和）
此題也可用離線||(其實這是官解)||
- 這方法常數大，~~可用pragma壓常數~~
----
Code(前置部分)
```cpp=
struct node
{
int val=0;
node *lc=0,*rc=0;
void pull()
{
val=0;
for (auto i : {lc,rc})
if (i) val+=i->val;
}
} *rt=0;
```
----
Code(修改及詢問)
```cpp=
void update(node*& cur,int l,int r,int i,int x)
{
if (!cur) cur=new node;
if (l+1==r)
{
cur->val+=x;
return;
}
if (i<mid) update(cur->lc,l,mid,i,x);
else update(cur->rc,mid,r,i,x);
cur->pull();
}
int query(node*& cur,int l,int r,int ql,int qr)
{
if (qr<=l || ql>=r || !cur) return 0;
if (ql<=l && r<=qr) return cur->val;
return query(cur->lc,l,mid,ql,qr)+query(cur->rc,mid,r,ql,qr);
}
```
----
AC code
```cpp=
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,ssse3,sse4,avx,avx2")
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define mid (l+r)>>1
using namespace std;
constexpr int MAXN=1e9+5;
struct node
{
int val=0;
node *lc=0,*rc=0;
void pull()
{
val=0;
for (auto i : {lc,rc})
if (i) val+=i->val;
}
} *rt=0;
void update(node*& cur,int l,int r,int i,int x)
{
if (!cur) cur=new node;
if (l+1==r)
{
cur->val+=x;
return;
}
if (i<mid) update(cur->lc,l,mid,i,x);
else update(cur->rc,mid,r,i,x);
cur->pull();
}
int query(node*& cur,int l,int r,int ql,int qr)
{
if (qr<=l || ql>=r || !cur) return 0;
if (ql<=l && r<=qr) return cur->val;
return query(cur->lc,l,mid,ql,qr)+query(cur->rc,mid,r,ql,qr);
}
int a[200005];
signed main()
{
colinorz;
int n,q; cin >> n >> q;
for (int i=1;i<=n;i++)
{
cin >> a[i];
update(rt,1,MAXN,a[i],1);
}
while (q--)
{
char op; int k,x;
if (cin>>op>>k>>x && op=='!')
{
update(rt,1,MAXN,a[k],-1);
a[k]=x;
update(rt,1,MAXN,a[k],1);
}
else cout << query(rt,1,MAXN,k,x+1) << endl;
}
}
```
---
# 謝謝大家
{"contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":9180,\"del\":531}]","title":"線段樹2","description":"by:hush"}