# Segment Tree

-----------
:::spoiler 區間和模板

#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. 初始化

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. 區間查詢

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. 單點修改

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. 懶人標記(區間修改)

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>

#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表最大元素的位置

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

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)橫排的最大值

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>

#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;
}