---
tags: Coding
---
# 樹
## 線段樹 (算區間最大值)
迴圈執行方式
像是dfs一樣，先挖到底然後再回頭挖沒挖過的地方
### 空間
接著要來想一下陣列該開多大，也就是節點編號最多會用到多少。一棵有 $2^i$（$i$ 是非負整數）個葉節點的滿二元樹，它的非葉節點會有 $2^i-1$ 個，因此它的總節點數是 $2^{i+1}-1$。線段樹的葉節點數和序列長度是一樣的，如果這個數字是 $n$，那麼葉節點會有 $n$ 個，最後一層填滿的話，應該會有 $2^{\lceil\log_2n\rceil}$ 個葉節點，因此整棵樹會有 $2^{\lceil\log_2n\rceil+1}-1$ 個節點。

如果 $n=2^i+a$，$0<a<2^i$，那麼 $2^{\lceil\log_2n\rceil}=2^{i+1}$，$2^{\lceil\log_2n\rceil+1}-1=2^{i+2}-1<2^{i+2}$，由此可知，$n \times 4$ 一定會大於總節點數，因此陣列大小通常都會取 $n \times 4$。

### 區間最大值
主程式

#include <bits/stdc++.h>
using namespace std;
const int N = 6;

struct segment_tree {
    int ch, value;
};

int arr[N] = {1, 2, 3, 4, 5, 6};
segment_tree st[4 * N];

// 懶人標記向下壓
void push(int lson, int rson, int index) {
    st[index].value = st[index].ch;
    if (st[index].ch > 0) {
        if (lson > 0) st[lson].ch = st[index].ch;
        if (rson > 0) st[rson].ch = st[index].ch;
    }
    st[index].ch = 0;
}

// 建樹
void build(int l, int r, int index) {
    if (l == r) {
        cout << l;
        st[index].value = arr[l];
    } else {
        int mid = (l + r) / 2, lson = index * 2, rson = index * 2 + 1;
        build(l, mid, lson);
        build(mid + 1, r, rson);
        st[index].value = max(st[lson].value, st[rson].value);
    }
}

// 區間查詢
int query(int a, int b, int l, int r, int index) {
    int mid = (l + r) / 2, lson = index * 2, rson = index * 2 + 1;
    if(l==r)lson=rson=-1;
    push(lson,rson,index);//沒有用到懶標的話這行跟上面那行就不用打
    if (a <= l && b >= r) {
        return st[index].value;
    } else {
        if (a > mid) {
            return query(a, b, mid + 1, r, rson);
        } else if (b <= mid) {
            return query(a, b, l, mid, lson);
        } else {
            return max(query(a, b, mid + 1, r, rson), query(a, b, l, mid, lson));
        }
    }
    return -1;
}

// 單點修改
void change_onepoint(int ch, int pos, int l, int r, int index) {
    if (pos == l && pos == r) {
        st[index].value = ch;
    } else {
        int mid = (l + r) / 2, lson = index * 2, rson = index * 2 + 1;
        if (pos > mid) {
            change_onepoint(ch, pos, mid + 1, r, rson);
        } else if (pos <= mid) {
            change_onepoint(ch, pos, l, mid, lson);
        }
        st[index].value = max(st[lson].value, st[rson].value);
    }
    return;
}

// 區間改值 利用懶標
void change_interval(int ch, int a, int b, int l, int r, int index) {
    int mid = (l + r) / 2, lson = index * 2, rson = index * 2 + 1;
    if (l == r) rson = lson = -1;
    push(lson, rson, index);
    if (a <= l && b >= r) {
        st[index].ch = ch;
    } else if (a > r || b < l) {
        return;
    } else {
        change_interval(ch, a, b, mid + 1, r, rson);
        change_interval(ch, a, b, l, mid, lson);
        int x1 = st[lson].ch == 0 ? st[lson].value : st[lson].ch;
        int x2 = st[rson].ch == 0 ? st[rson].value : st[rson].ch;
        st[index].value = max(x1, x2);
    }
    return;
}

void look(int t) {
    int k = 1;
    cout << endl;
    for (int i = 1; i < N * 4; i++) {
        if (!t)
            cout << st[i].value << " ";
        else
            cout << st[i].ch << " ";
        if (i == k) {
            cout << endl;
            k = k * 2 + 1;
        }
    }
    cout << endl;
}

signed main() {
    for (int i = 0; i < 4 * N; i++) {
        st[i].ch = 0;
    }
    build(0, N - 1, 1);  // 初始化 建樹
    look(0);
    cout << query(2, 4, 0, N - 1, 1) << endl;
    change_onepoint(11, 3, 0, N - 1, 1);  // 改一個值
    look(0);
    change_interval(13, 0, 1, 0, N - 1, 1);
    look(0);
    look(1);
    cout << query(4, 7, 0, N - 1, 1);
    return 0;
}

**犯蠢紀錄**
if (l == r) rson = lson = -1;打成if (a == l && b == r) rson = lson = -1;原本是子葉不用下推，卻寫成到想要的區域沒有下推。

## Bit tree (Fenwick tree 算區間和)
定義lowbit(x)為x&(-x)
bit[x]中存arr[x-lowbit(x)+1]到arr[x]所有數的和。

update原理：
每一次update只更新有包含到區間。例如改變位置13，則有包含的區間為(13),(13\~14),(1\~16)。還好有一個特別的方法，x加上x&(-x)就可以剛好從13到14,14到16。x&(-x)其實就是取最右邊的1與其後面的0，例如0100100取完就是0000100
[圖片取自](https://yuihuang.com/binary-indexed-tree/)

void update(int index,int val){
    while(index<=N){
        bit[index]+=val;
        index+=index&(-index);
    }
}

query查詢原理：
由下往上加，如果查詢x前綴和。剛好可以用x-x&(-x)來把依序相加。例子中13的前綴和就是bit[13]+bit[12]+bit[8]。

查詢

int query(int index){
    int val=0;
    while(index>0){
        val+=bit[index];
        index-=index&(-index);
    }
    return val;
}

初始化就是從原本給的數據中一個一個給update更新。

初始化

for(int i=1;i<=N;i++){
    update(i,arr[i-1]);
}

主程式

const int N=9;
int arr[N]={1,2,3,4,5,6,7,8,9};
int bit[N];

void update(int index,int val){
    while(index<=N){
        bit[index]+=val;
        index+=index&(-index);
    }
}

int query(int index){
    int val=0;
    while(index>0){
        val+=bit[index];
        index-=index&(-index);
    }
    return val;
}

int main(){
    for(int i=1;i<=N;i++){
        update(i,arr[i-1]);
    }
    
    for(int i=1;i<=N;i++){
        cout<<bit[i]<<" ";
    }
    cout<<endl<<query(4);
    return 0;
}