# Segment Tree
-----------
:::spoiler 區間和模板
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100005
int sum[MAXN * 4], lazy[MAXN * 4];
int a[MAXN], n, m;
void push_down(int now, int l, int r) {
int L = now * 2, R = now * 2 + 1, val = lazy[now], mid = (l + r) / 2;
sum[L] += (mid - l + 1) * val;
sum[R] += (r - mid) * val;
lazy[L] += val;
lazy[R] += val;
lazy[now] = 0;
}
void built(int now = 1, int l = 1, int r = n) {
if (l == r) {
sum[now] = a[l];
return;
}
int mid = (l + r) / 2;
built(now * 2, l, mid);
built(now * 2 + 1, mid + 1, r);
sum[now] = sum[now * 2] + sum[now * 2 + 1];
}
void update_range(int lb, int rb, int val, int now = 1, int l = 1, int r = n) {
if (lb <= l && r <= rb) {
sum[now] += val * (r - l + 1);
lazy[now] += val;
return;
}
push_down(now, l, r);
int mid = (l + r) / 2;
if (lb <= mid)
update_range(lb, rb, val, now * 2, l, mid);
if (mid + 1 <= rb)
update_range(lb, rb, val, now * 2 + 1, mid + 1, r);
sum[now] = sum[now * 2] + sum[now * 2 + 1];
}
int query_range(int lb, int rb, int now = 1, int l = 1, int r = n) {
if (lb <= l && r <= rb)
return sum[now];
push_down(now, l, r);
int mid = (l + r) / 2, ans = 0;
if (lb <= mid)
ans += query_range(lb, rb, now * 2, l, mid);
if (mid + 1 <= rb)
ans += query_range(lb, rb, now * 2 + 1, mid + 1, r);
return ans;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
built();
while (m--) {
int index;
cin >> index;
if (index == 1) {
int l, r, val;
cin >> l >> r >> val;
update_range(l, r, val);
} else {
int l, r;
cin >> l >> r;
cout << query_range(l, r) << '\n';
}
}
}
```
:::
-----------
線段樹
求區間最值,區間總和,區間gcd
陣列要開至少4*MAXN,也就是MAXN << 2
1. 初始化
```cpp=
int seg[MAXN << 2];
void built(int node,int l,int r){
if(l==r){
seg[node]=a[l];
return;
}
int mid=l+r>>1;
built(node<<1,l,mid);
built(node<<1|1,mid+1,r);
seg[node]=min(seg[node<<1],seg[node<<1|1]);
}
```
2. 區間查詢
```cpp=
int query(int node,int l,int r,int Lb,int Rb){
if(Lb<=l && r<=Rb) return seg[node];
int mid=l+r>>1,result=inf;
if(Lb<=mid) result=min(result,query(node<<1,l,mid,Lb,Rb));
//如果mid在左邊界(Lb)的右邊,代表左半邊[i,mid]有在要查詢的區間內,執行遞迴
if(mid+1<=Rb) result=min(result,query(node<<1|1,mid+1,r,Lb,Rb));
//如果mid+1在右邊界(Rb)的左邊,代表右半邊[mid+1,j]有在要查詢的區間內,執行遞迴
return result;
}
```
3. 單點修改
```cpp=
int update(int node,int l,int r,int target,int val){
if(l==r){
seg[node]=val;
return;
}
int mid=l+r>>1;
if(target<=mid) update(node<<1,l,mid,Lb,Rb); //如果要修改的點在左邊就遞迴左邊
else update(node<<1|1,mid+1,r,Lb,Rb);//否則在右邊
seg[node]=min(seg[node<<1],seg[node<<1|1]); //更新最小值
}
```
3. 懶人標記(區間修改)
```cpp=
void pushdown(int node,int L,int R){
if(lazy[node]==0) return;
laxy[node*2+1]+=lazy[node];
lazy[node*2+2]+=lazy[node];
tree[node*2+1]+=lazy[node]*L;
tree[node*2+2]+=lazy[node]*R;
lazy[node]=0;
}
void modify(int node,int L,int R,int lb,int rb,int add){
if(Lb<=l && r<=Rb){
tree[node]+=add;
lazy+=add;
return;
}
int mid=(L+R)/2;
pushdown(node,mid-L+1,R-mid);
if(lb<=mid) modify(node*2+1,L,mid, lb,rb,add);
if(mid+1<=rb) modify(node*2+2,mid+1,R, lb,rb,add);
tree[node]=tree[node*2+1]+tree[node*2+2];
}
```
<a href="https://zerojudge.tw/ShowProblem?problemid=d539">ZJ d539: 區間 MAX</a>
```cpp=
#include <bits/stdc++.h>
using namespace std;
int seg[500000 << 2]={0};
void update(int node ,int l,int r,int target,int val){
if(l==r){
seg[node]=val;
return;
}
int mid=(l+r)/2;
if(target<=mid){
update(node*2+1,l,mid,target,val);
}else{
update(node*2+2,mid+1,r,target,val);
}
seg[node]=max(seg[node*2+1],seg[node*2+2]);
return;
}
int query(int node,int l,int r,int i,int j){
if(l==i && r==j || l==r) return seg[node];
int mid=(l+r)/2;
if(j<=mid){
return query(node*2+1,l,mid,i,j);
}else if(i>mid){
return query(node*2+2,mid+1,r,i,j);
}else{
return max(
query(node*2+1,l,mid,i,mid),query(node*2+2,mid+1,r,mid+1,j));
}
}
int main(){
cin.sync_with_stdio(0),cin.tie(0);
int n,x;
cin >> n;
for(int i=0;i<n;i++){
cin >> x;
update(0,0,n-1,i,x);
}
int t;
cin >> t;
while(t--){
int x,y;
cin >> x >> y;
if(x>y) swap(x,y);
cout << query(0,0,n-1,x-1,y-1) << '\n';
}
return 0;
}
```
## 二維線段數
在這之前要先介紹一個函式:max_element
參數為:max_element(起始位置,終點位置+1);
回傳值:一個iterator表最大元素的位置
```cpp=
vector<int> v{1,5,4,7,8,3,2,6};
int result = *max_element(v.begin(),v.end());
//result = 8
```
其實二維線段樹和一維差別不大,以下是我畫的示意圖
a是測資,後面的括號是其座標,每一直行都是一顆一維線段樹,以(3,2)為例,其用陣列的表示法就是seg[node][2],node就是在一維線段樹裡的遞迴(上下移動),所以當我們要求區域最大值時,就先遞迴找(L,R),再用max_element把橫的陣列取最大值,也就是說,先用一維線段樹找到每一直行的最大值,再把所有直行的最大值取最大值就是答案了
### 更新
j完全不動,因為是在第j棵線段樹裡遞迴i
```cpp=
void update(int node ,int l,int r,int i,int j,int val){
if(l==r){
seg[node][j]=val;
return;
}
int mid=(l+r)/2;
if(i<=mid){
update(node*2+1,l,mid,i,j,val);
}else{
update(node*2+2,mid+1,r,i,j,val);
}
seg[node][j]=max(seg[node*2+1][j],seg[node*2+2][j]);
return;
}
```
### 查詢
先遞迴找(i1,i2),再用max_element找(j1,j2)橫排的最大值
```cpp=
int query(int node,int l,int r,int i1,int i2,int j1,int j2){
if(l==i1 && r==i2){
return *max_element(seg[node]+j1,seg[node]+j2+1);
}
int mid=(l+r)/2;
if(i2<=mid){
return query(node*2+1,l,mid,i1,i2,j1,j2);
}else if(i1>mid){
return query(node*2+2,mid+1,r,i1,i2,j1,j2);
}else{
return max(
query(node*2+1,l,mid,i1,mid,j1,j2),query(node*2+2,mid+1,r,mid+1,i2,j1,j2));
}
}
```
<a href="https://zerojudge.tw/ShowProblem?problemid=d798">ZJ d798: 區域MAX</a>
```cpp=
#include <bits/stdc++.h>
#define MAXN 505
using namespace std;
int seg[MAXN << 2][MAXN << 2]={0};
void update(int node ,int l,int r,int i,int j,int val){
if(l==r){
seg[node][j]=val;
return;
}
int mid=(l+r)/2;
if(i<=mid){
update(node*2+1,l,mid,i,j,val);
}else{
update(node*2+2,mid+1,r,i,j,val);
}
seg[node][j]=max(seg[node*2+1][j],seg[node*2+2][j]);
return;
}
int query(int node,int l,int r,int i1,int i2,int j1,int j2){
if(l==i1 && r==i2){
return *max_element(seg[node]+j1,seg[node]+j2+1);
}
int mid=(l+r)/2;
if(i2<=mid){
return query(node*2+1,l,mid,i1,i2,j1,j2);
}else if(i1>mid){
return query(node*2+2,mid+1,r,i1,i2,j1,j2);
}else{
return max(
query(node*2+1,l,mid,i1,mid,j1,j2),query(node*2+2,mid+1,r,mid+1,i2,j1,j2));
}
}
int main(){
cin.sync_with_stdio(0),cin.tie(0);
int n,m,x;
cin >> n >> m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin >> x;
update(0,0,n-1,i,j,x);
}
}
int t;
cin >> t;
while(t--){
int i1,i2,j1,j2;
cin >> i1 >> i2 >> j1 >> j2;
cout << query(0,0,n-1,i1-1,j1-1,i2-1,j2-1) << '\n';
}
return 0;
}
```
Sign in with Wallet
Connect another wallet