# 線段樹

> [color=blue]於競賽而言強大的工具。

## 用法 & 概念

線段樹除了可以用來快速解區間和問題，還可以用來執行許多與區間有關的操作。大致上用以下方式建構區間

digraph SEG{
    nodesep=0.7 // increases the separation between nodes
                
    node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
    edge [color=Blue, style=dashed] //All the lines look like this

    "1~8"->{"1~4" "5~8"}
        "1~4"->{"1~2" "3~4"}
            "1~2"->{"1" "2"}
            "3~4"->{"3" "4"}
            
        "5~8"->{"5~6" "7~8"}
            "5~6"->{"5" "6"}
            "7~8"->{"7" "8"}
}

每個區間視情況放不同的數值，例如：最大/小，或是區間總和等。

接著，每個區間就都可以分為$O(log(n))$個區間，例如`2~7`可以分為`2, 3~4, 5~6, 7`

digraph SEG{
    nodesep=0.7 // increases the separation between nodes
                
    node [color=Red,fontname=Courier,shape=box] //All nodes will this shape and colour
    edge [color=Blue, style=dashed] //All the lines look like this

    "1~8"->{"1~4" "5~8"}
        "1~4"->{"1~2" "3~4"[color=DarkGreen]}
            "1~2"->{"1" "2"[color=DarkGreen]}
            "3~4"->{"3" "4"}
            
        "5~8"->{"5~6"[color=DarkGreen] "7~8"}
            "5~6"->{"5" "6"}
            "7~8"->{"7"[color=DarkGreen] "8"}
}

查詢時皆以最大區間為出發點，例如上圖就會是從`1~8`這個區間開始，如果要查詢的區間是`2~7`。因為`1~8`這個區間並沒有完全包含`2~7`，因此需要往下遞迴，分成`1~4`和`5~8`再次查詢。

接著，因為`1~4`和`5~8`仍然沒有完全被`2~7`包含，因此要再次遞迴，這次是分解成`1~2`,`3~4`,`5~6`以及`7~8`。

這次`3~4`和`5~6`都有被完全包含，因此可以直接回傳這個區間的值。而`1~2`和`7~8`還是沒有。所以這兩個區間還要再次向下查詢。

查詢時最重要的是，若區間完全被包含就直接回傳，若完全沒被包含就不往那邊搜尋，否則再將區間分成兩塊向下遞迴。

## 實作

可以發現他是一顆二元樹，於是我們有兩種做法：指標型與陣列型。以下實作以區間總和為範例。

### 指標型

請詳讀程式碼，我盡可能詳細註解

#include<bits/stdc++.h>
using namespace std;

int n;

struct node{
    //value
    int val;

    //左右子樹的指標
    node *rch,*lch;
    
    //建構式
    node(){
        val=0;
        rch=lch=nullptr;
    }

    //帶有初始值的建構式
    node(int v){
        val=v;
        rch=lch=nullptr;
    }

    //當左右子樹改變時，應重新計算父節點的值
    void pull(){
        //歸零
        val=0;
        //必須先有左右子樹才能拜訪
        //if(l) 相當於 if(l!=nullptr)
        if(lch) val+=lch->val;
        if(rch) val+=rch->val;
    }

    //單點修改
    void modify(int p,int v,int lb=1,int rb=n){
        //終止條件：區間長度為1
        if(lb==rb){
            val=v;
            return;
        }

        //若左右子樹沒有結點則開一個新的
        if(!lch) lch=new node();
        if(!rch) rch=new node();

        //設mid為區間中點，均分為左右區間
        //>>1相當於/2，但快很多
        int mid=lb+rb>>1;

        //左邊走左，右邊走右
        if(p<=mid) lch->modify(p,v, lb ,mid);
        if(mid<p)  rch->modify(p,v,mid+1,rb);

        //還記得子樹修改完要做什麼？
        pull();
    }

    int query(int l,int r,int lb=1,int rb=n){
        //終止條件：所在區間位於欲查詢區間之中
        if(l<=lb && rb<=r){
            return val;
        }

        //同modify
        int mid=lb+rb>>1;

        //左右遞迴求解
        int ret=0;
        //若左右區間不在要查詢的區間或是沒有左右子樹則不遞迴
        if(lch && l<=mid) ret+=lch->query(l,r, lb ,mid);
        if(rch && mid<r)  ret+=rch->query(l,r,mid+1,rb);

        //為求保險，以及供以後懶人標記使用
        pull();

        return ret;
    }
};

node *rt=new node();//root

### 陣列型

> [color=blue] **設根節點idx為1，在完滿二元樹中，左子樹就會是$idx \times 2$，右子樹就是$idx \times 2+1$。**

#include<bits/stdc++.h>
using namespace std;

const int N=100010;

int a[N];
//陣列seg的大小建議是N*4，否則你要先知道大於N的最小2^k值
// 131072 -> 262144 所以其實開 262200 就可以了
int seg[N*4];
int n,MXN=1;

//不同於指標型的是：陣列行要預建構
void build(int lb=1,int rb=MXN,int idx=1){
    //終止條件：區間長度為1
    if(lb==rb) return;
    
    //設mid為區間中點，均分為左右區間
    //>>1相當於/2，但稍快
    int mid=lb+rb>>1;
    
    //idx*2   為左子樹
    //idx*2+1 為右子樹
    build(lb,mid,idx*2);
    build(mid+1,rb,idx*2+1);
    
    seg[idx]=seg[idx*2]+seg[idx*2+1];
}

void init(){
    //為了讓他長度為2^k
    while(MXN<n) MXN<<=1;
    //歸零
    for(int i=MXN+1;i<MXN*2;i++) seg[i]=0;
    //以陣列的內容對其初始化
    for(int i=1;i<=n;++i) seg[MXN+i-1]=a[i];
    //將所有節點都建構好
    build();
} 

void modify(int x,int k){
    //此部分也與指標型不同，陣列可以直接依據座標修改
    x=x+MXN-1;
    seg[x]=k;
    
    //向上更新節點
    while(x>1){
        x>>=1;
        seg[x]=seg[x*2]+seg[x*2+1];
    }
}

int query(int l,int r,int lb=1,int rb=MXN,int idx=1){
    //終止條件：所在區間位於欲查詢區間之中
    if(l<=lb && rb<=r) return seg[idx];
    
    //設mid為區間中點，均分為左右區間
    //>>1相當於/2，但稍快
    int mid=lb+rb>>1;

    //左右遞迴求解
    int ret=0;
    
    //若左右區間不在要查詢的區間或是沒有左右子樹則不遞迴
    if(l<=mid)   ret+=query(l,r, lb ,mid,idx*2);
    if(r>=mid+1) ret+=query(l,r,mid+1,rb,idx*2+1);
    
    return ret;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    //一定要記得init()
    init();
}

## 懶人標記
以上的實作方法都只能用於單點修改，而若需要區間加值的話則會很費時，因此有人想到一個方法：若要修改的區間剛好完全包含線段樹上的某個區間的話，就可以先在上面打一個標記。等到需要動到他下面的子區間再向下放。這樣的話區間加值也可以從 $O(nlog(n))$ 進步到 $O(log(n))$ 。

### 實作

#### 指標型

請詳讀程式碼，我盡可能詳細註解

#include<bits/stdc++.h>
using namespace std;

int n;

struct node{
    //value tag
    int val,tag;

    //左右子樹的指標
    node *rch,*lch;
    
    //建構式
    node(){
        val=tag=0;
        rch=lch=nullptr;
    }

    //帶有初始值的建構式
    node(int v){
        val=v, tag=0;
        rch=lch=nullptr;
    }

    //多了一個push()，將標記下放
    void push(int l,int r){
        //>>運算會在+-之後
        int len=r-l+1>>1;
        if(lch){
            lch->val+=tag*len;
            lch->tag+=tag;
        }
        
        if(rch){
            rch->val+=tag*len;
            rch->tag+=tag;
        }
        tag=0;
    }
    
    //當左右子樹改變時，應重新計算父節點的值
    void pull(){
        //歸零
        val=0;
        //必須先有左右子樹才能拜訪
        //if(l) 相當於 if(l!=nullptr)
        if(lch) val+=lch->val;
        if(rch) val+=rch->val;
    }

    //單點修改
    void modify(int p,int v,int lb=1,int rb=n){
        //終止條件：區間長度為1
        if(lb==rb){
            val=v;
            return;
        }

        //若左右子樹沒有結點則開一個新的
        if(!lch) lch=new node();
        if(!rch) rch=new node();

        //在遞迴之前先下放標記
        push(lb,rb);
        
        //設mid為區間中點，均分為左右區間
        //>>1相當於/2，但快很多
        int mid=lb+rb>>1;

        //左邊走左，右邊走右
        if(p<=mid) lch->modify(p,v, lb ,mid);
        if(mid<p)  rch->modify(p,v,mid+1,rb);

        //還記得子樹修改完要做什麼？
        pull();
    }

    int query(int l,int r,int lb=1,int rb=n){
        //終止條件：所在區間位於欲查詢區間之中
        if(l<=lb && rb<=r){
            return val;
        }

        //在遞迴之前先下放標記
        push(lb,rb);
        
        //同modify
        int mid=lb+rb>>1;

        //左右遞迴求解
        int ret=0;
        //若左右區間不在要查詢的區間或是沒有左右子樹則不遞迴
        if(lch && l<=mid) ret+=lch->query(l,r, lb ,mid);
        if(rch && mid<r)  ret+=rch->query(l,r,mid+1,rb);

        pull();

        return ret;
    }
    
    //多了一個函式，區間加值
    void add(int l,int r,int v,int lb=1,int rb=n){
        //終止條件：所在區間位於欲查詢區間之中
        if(l<=lb && rb<=r){
            //由於區間為閉區間[lb,rb]因此要加1
            val+=v*(rb-lb+1);
            tag+=v;
            return;
        }

        //在遞迴之前先下放標記
        push(lb,rb);
        
        //同modify
        int mid=lb+rb>>1;

        //左右遞迴求解
        int ret=0;
        //若左右區間不在要查詢的區間或是沒有左右子樹則不遞迴
        if(lch && l<=mid) lch->add(l,r,v, lb ,mid);
        if(rch && mid<r)  rch->add(l,r,v,mid+1,rb);

        pull();
    }
};

node rt;//root

## 習題

### [Segment Tree 練習(ZJe409)](https://zerojudge.tw/ShowProblem?problemid=e409)

#### 題目概述 :
將 $A[x]$的值更新為 $y$
要查詢 $A[X]$~$A[Y]$ 之中最大值$maxA$及最小值$minA$的差

#### 輸入說明 :
第1列有兩個正整數 $k$ $m$ ，第2列有 $k$ 個正整數, 請讀入放至 $A[1..k]$
接著讀入第3列的 $N$ $Q$ 兩個正整數，呼叫所附的產生測資程式 `gen_dat()`
以上 $5<k \leq n, 5<m<1000$
然後就是解題，依$C,X,Y$陣列的值 執行更新或查詢

#### 輸出說明 :
若為調查，則輸出區域中的元素總和，若為修改，則不必輸出

#### 範例輸入 1 :

10 541
12 34 56 78 91 23 45 67 89 111
25 15

#### 範例輸出 1 :

328
68
406
0
79
251
327
489
0

---

### [戰術資料庫(110宜中資訊社校內賽pF)](https://zerojudge.tw/ShowProblem?problemid=g625)

#### 題目敘述 :
要求能在一個陣列中做以下操作

1. 搜尋區間和 $find sum$ $(l)$ $(r)$
2. 搜尋區間最大和最小值 $find$ $max/min (l)$ $(r)$
3. 單點加減值 $plus/minus$ $(position)$ $(k)$

#### 輸入說明 :
輸入第一行有一個數字 n, q ，下一行有 n 個數字，緊接著有 q 筆操作，可能為以下五種
1. 搜尋區間和
2. 搜尋區間最大和最小值
3. 單點加減值

相鄰數字間以空白隔開。
$n, q \leq 100000 , a[i] \leq 100000$

#### 輸出說明 :
對於每個搜尋指令做出回答

#### 範例輸入 1 :

7 10
1 2 3 4 5 6 7
find max 2 5
find min 1 4
minus 3 1
plus 2 4
find sum 1 7
plus 7 -3
find sum 1 3
minus 6 0
plus 1 1
find max 1 7

#### 範例輸出 1 :

5
1
31
9
6

> **2022/1/10**
> [name=mtmatt] [time=Mon, Jan 10, 2022 21:10 ] [color=#00eeff]