---
# System prepended metadata

title: CSES Range Queries(25 題)

---

# Range Queries(25 題)
## Static Range Sum Queries [problem](https://cses.fi/problemset/task/1646)
```markdown
題目: 

給定一個長度為 n 的整數陣列，以及 m 組查詢，每次查詢請輸出區間 [a, b] 內所有數字的總和。
```
``` markdown
解法 : 

這是一題經典的前綴和問題，先用 prefix[i] 表示前 i 項的總和，
那麼任意區間 [a, b] 的總和就可以用 prefix[b] - prefix[a-1] 得到。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

signed main(){
    fastio;

    int n, m;
    cin >> n >> m;
    vector<int> prefix(n + 1, 0);

    for(int i = 1; i <= n; ++i){
        int num; cin >> num;
        prefix[i] = num + prefix[i - 1];
    }

    while(m--){
        int a, b;
        cin >> a >> b;
        cout << prefix[b] - prefix[a - 1] << '\n';
    }
    return 0;
}
```

## Static Range Minimum Queries [problem](https://cses.fi/problemset/task/1647)
```markdown
題目: 

- 給定一個長度為 n 的整數陣列。
- 接著有 m 筆查詢，每次查詢給一段區間 [a, b]，請輸出該區間內的最小值。
- 資料不會修改，屬於**靜態 RMQ 問題**。
```
``` markdown
解法 : 

### 1. Segment Tree 預處理
- 對原始陣列建 Segment Tree，記錄每個區間的最小值。
- 查詢時透過 divide-and-conquer 往左右子樹查詢交集區間。

---

### 2. 操作說明
- `build()`：遞迴建樹。
- `query()`：查詢區間最小值。
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int MAXN = 2e5 + 5;
int n, q;
int a[MAXN];
int seg[4 * MAXN];

void build(int node, int l, int r) {
    if (l == r) {
        seg[node] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    seg[node] = min(seg[2 * node], seg[2 * node + 1]);
}

int query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return INT_MAX;
    if (ql <= l && r <= qr) return seg[node];
    int mid = (l + r) / 2;
    return min(query(2 * node, l, mid, ql, qr),
               query(2 * node + 1, mid + 1, r, ql, qr));
}

int main() {
    fastio;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i];
    build(1, 0, n - 1);
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << query(1, 0, n - 1, l - 1, r - 1) << '\n';
    }
}
```

## Dynamic Range Sum Queries [problem](https://cses.fi/problemset/task/1648)
```markdown
題目: 

- 有一個長度為 n 的整數陣列。
- 操作共分兩種：
  1. 將第 a 個數字更新為 b。
  2. 查詢某區間 [a, b] 的總和。
- 要處理 m 筆操作，且需在快時間內完成。
```
``` markdown
解法 : 

### 1. Segment Tree + 單點更新
- 因為每次更新只針對單一點（a 變成 b），不需要區間加法或乘法。
- 可以使用 Segment Tree 並進行 **單點賦值操作（point update）**。
- 查詢則為區間加總（range sum）。

---

### 2. 實作說明
- 為了復用 Lazy Segment Tree 的模板，這份程式碼套用了「區間賦值 + 區間加總」的通用寫法。
- 在初始化時，將每個數字作為區間長度為 1 的賦值操作。
- 在更新時，也僅更新單點 (a = b)。
- 雖然 lazy 多此一舉。
```

``` cpp
#include <bits/stdc++.h>
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
struct LazySegTree {
    int n;
    vector<long long> tree, lazy;
 
    LazySegTree(int size) {
        n = size;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }
 
    void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            tree[node] = (r - l + 1) * lazy[node];
            if (l != r) {
                lazy[2 * node] = lazy[node];
                lazy[2 * node + 1] = lazy[node];
            }
            lazy[node] = 0;
        }
    }
 
    void update(int node, int l, int r, int ul, int ur, long long val) {
        push(node, l, r);
        if (r < ul || ur < l) return;
        if (ul <= l && r <= ur) {
            lazy[node] = val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ul, ur, val);
        update(2 * node + 1, mid + 1, r, ul, ur, val);
        tree[node] = (tree[2 * node] + tree[2 * node + 1]);
    }
 
    long long query(int node, int l, int r, int ql, int qr) {
        push(node, l, r);
        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return (query(2 * node, l, mid, ql, qr)
             + query(2 * node + 1, mid + 1, r, ql, qr));
    }
 
    // wrapper functions
    void add(int l, int r, long long val) {
        update(1, 0, n - 1, l, r, val);
    }
 
    long long range_sum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};
 
int main(){
    fastio;
    int n, m;
    cin >> n >> m;
    LazySegTree st(n);
    for(int i = 0; i < n; ++i){
        int num; cin >> num;
        st.add(i, i, num);
    }
 
    while(m--){
        int c, a, b;
        cin >> c >> a >> b;
        if(--c) {
            cout << st.range_sum(a - 1, b - 1) << '\n';
        } else {
            st.add(a - 1, a - 1, b);
        }
    }
}
```

## Dynamic Range Minimum Queries [problem](https://cses.fi/problemset/task/1649)
```markdown
題目: 

- 給你一個長度為 n 的整數陣列。
- 有 m 筆操作，操作包含兩種：
  1. 更新第 a 個位置的值為 b。
  2. 查詢區間 [a, b] 的最小值。
- 要求高效地完成所有操作。
```
``` markdown
解法 : 

### 1. Segment Tree + 單點更新
- 使用 Segment Tree 解決區間最小值查詢。
- 此模板用 Lazy Propagation 架構撰寫，但實際操作只有單點更新（區間長度為 1 的賦值）。

---

### 2. 資料結構說明
- `tree[]`: 儲存每個區間的最小值。
- `lazy[]`: 預設為 -1，僅用於懶標記區間賦值。
- `add(l, r, val)`: 更新區間 [l, r] 的值為 val，這題中實際上只會呼叫 `add(i, i, val)`。
- `range_sum(l, r)`: 查詢區間最小值（其實是 `range_min()`，命名只是保留模板習慣）。
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
struct LazySegTree {
    int n;
    vector<long long> tree, lazy;
 
    LazySegTree(int size) {
        n = size;
        tree.assign(4 * n, LLONG_MAX);
        lazy.assign(4 * n, -1);
    }
 
    void push(int node, int l, int r) {
        if (lazy[node] != -1) {
            tree[node] = lazy[node];
            if (l != r) {
                lazy[2 * node] = lazy[node];
                lazy[2 * node + 1] = lazy[node];
            }
            lazy[node] = -1;
        }
    }
 
    void update(int node, int l, int r, int ul, int ur, long long val) {
        push(node, l, r);
        if (r < ul || ur < l) return;
        if (ul <= l && r <= ur) {
            lazy[node] = val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ul, ur, val);
        update(2 * node + 1, mid + 1, r, ul, ur, val);
        tree[node] = min(tree[2 * node] , tree[2 * node + 1]);
    }
 
    long long query(int node, int l, int r, int ql, int qr) {
        push(node, l, r);
        if (r < ql || qr < l) return LLONG_MAX;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return min(query(2 * node, l, mid, ql, qr)
             , query(2 * node + 1, mid + 1, r, ql, qr));
    }
 
    // wrapper functions
    void add(int l, int r, long long val) {
        update(1, 0, n - 1, l, r, val);
    }
 
    long long range_sum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};
 
int main(){
    fastio;
    int n, m;
    cin >> n >> m;
    LazySegTree st(n);
    for(int i = 0; i < n; ++i){
        int num; cin >> num;
        st.add(i, i, num);
    }
 
    while(m--){
        int c, a, b;
        cin >> c >> a >> b;
        if(--c) {
            cout << st.range_sum(a - 1, b - 1) << '\n';
        } else {
            st.add(a - 1, a - 1, b);
        }
    }
}
```

## Range Xor Queries [problem](https://cses.fi/problemset/task/1650)
```markdown
題目: 

- 給定一個長度為 n 的陣列。
- 有 m 筆查詢，每次查詢一段區間 [a, b] 的 XOR 值。
- 所有查詢為靜態查詢，不包含修改。
```
``` markdown
解法 : 

### 1. 前綴 XOR 陣列（Prefix XOR）
- 定義 prefix[i] 為前 i 項的 XOR 結果，即 prefix[i] = a[1] ^ a[2] ^ ... ^ a[i]
- 區間 [a, b] 的 XOR 結果為：`prefix[b] ^ prefix[a - 1]`
- 原理同前綴和，只是把 `+` 換成了 `^`，且 XOR 符合交換與結合律。

---

### 2. 為何不用 Segment Tree？
- 因為這題資料不會被修改，屬於「純查詢」問題，使用 prefix array 更簡潔且效率更高。
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
int main(){
    fastio;
    int n, m;
    cin >> n >> m;
    
    vector<long long> prefix(n + 1, 0);
 
    for(int i = 1; i <= n; ++i){
        int num; cin >> num;
        prefix[i] = prefix[i - 1] ^ num;
    }
 
    while(m--){
        int a, b;
        cin >> a >> b;
        cout << (prefix[b] ^ prefix[a - 1]) << '\n';
    }
}
```

## Range Update Queries [problem](https://cses.fi/problemset/task/1651)
```markdown
題目: 

- 給你一個長度為 n 的整數陣列。
- 有兩種操作，共 m 筆：
  1. 將區間 [a, b] 中的每個數字加上某個值。
  2. 查詢某個位置的當前數值。
- 需要高效處理所有操作。
```
``` markdown
解法 : 

### 1. Lazy Segment Tree（支援區間加法 + 單點查詢）
- 標準 Segment Tree 無法快速處理區間加法 → 改用 Lazy Propagation。
- 區間加法時，用 lazy 陣列標記下推。
- 查詢時從上到下 push 過所有影響當前節點的 lazy。

---

### 2. 核心函數說明：
- `add(l, r, val)`：區間加法操作。
- `range_sum(l, r)`：查詢區間總和，這題中實際只會查詢單點 (l = r)。
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
struct LazySegTree {
    int n;
    vector<long long> tree, lazy;
 
    LazySegTree(int size) {
        n = size;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }
 
    void push(int node, int l, int r) {
        if (lazy[node] != 0) {
            tree[node] += (r - l + 1) * lazy[node];
            if (l != r) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
 
    void update(int node, int l, int r, int ul, int ur, long long val) {
        push(node, l, r);
        if (r < ul || ur < l) return;
        if (ul <= l && r <= ur) {
            lazy[node] = val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ul, ur, val);
        update(2 * node + 1, mid + 1, r, ul, ur, val);
        tree[node] = (tree[2 * node] + tree[2 * node + 1]);
    }
 
    long long query(int node, int l, int r, int ql, int qr) {
        push(node, l, r);
        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return (query(2 * node, l, mid, ql, qr)
             + query(2 * node + 1, mid + 1, r, ql, qr));
    }
 
    // wrapper functions
    void add(int l, int r, long long val) {
        update(1, 0, n - 1, l, r, val);
    }
 
    long long range_sum(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};
 
int main(){
    fastio;
    int n, m;
    cin >> n >> m;
    LazySegTree st(n);
    for(int i = 0; i < n; ++i){
        int num; cin >> num;
        st.add(i, i, num);
    }
 
    while(m--){
        int c;
        cin >> c;
        if(--c){
            int k;
            cin >> k;
            cout << st.range_sum(k-1, k-1) << '\n';
        } else {
            int a, b, num;
            cin >> a >> b >> num;
            st.add(a - 1, b - 1, num);
        }
    }
}
```

## Forest Queries [problem](https://cses.fi/problemset/task/1652)
```markdown
題目: 

- 給定一個 n × n 的地圖，每格是 `*`（代表一棵樹）或 `.`（空地）。
- 接著有 m 筆查詢，每次查詢矩形區域內有幾棵樹。
- 要求能在快速時間內處理所有查詢。
```
``` markdown
解法 : 

### 1. 2D 前綴和（Prefix Sum 2D）
- 建立一個 2D 陣列 `forest[y][x]`，代表從 (1,1) 到 (y,x) 區域內的樹木總數。
- 每格的值可以由以下公式計算：
  forest[i][j] = forest[i-1][j] + forest[i][j-1] - forest[i-1][j-1] + (s[j-1] == '*');
  
- 每次查詢 [y1, x1] 到 [y2, x2] 的總樹數為：
  forest[y2][x2] - forest[y1-1][x2] - forest[y2][x1-1] + forest[y1-1][x1-1]
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
int main(){
    fastio;
    int n, m;
    cin >> n >> m;
    
    vector<vector<long long>> forest(n + 1, vector<long long>(n + 1, 0));
 
    for(int i = 1; i <= n; ++i){
        string s;
        cin >> s;
        for(int j = 1; j <= n; ++j){
            forest[i][j] = forest[i - 1][j] + forest[i][j - 1] -
                forest[i - 1][j - 1] + (s[j - 1] == '*');
        }
    }
 
    while(m--){
        int x1, x2, y1, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        cout << forest[y2][x2] + forest[y1 - 1][x1 - 1] 
            - forest[y2][x1 - 1] - forest[y1 - 1][x2]<< '\n';
    }
}
```

## Hotel Queries [problem](https://cses.fi/problemset/task/1143)
```markdown
題目: 

- 有 n 間旅館，每間可容納的最大人數為 h₁, h₂, ..., hₙ。
- 有 m 組客人，每組人數為 a。
- 對每組客人，找最靠左的旅館且尚有足夠空間接待，並讓他們入住（容量減少）。
- 如果找不到，輸出 0；否則輸出該旅館的編號（從 1 開始）。
```
``` markdown
解法 : 

### 1. Segment Tree + Max + First-Above 查詢
- 每個節點維護區間內最大的剩餘容量。
- 對每組客人，從 root 開始往左右子樹找出 **最靠左且 ≥ a 的節點**。
- 找到後將該點減少 a，並回傳編號。

---

### 2. 實作要點
- 使用 Lazy Segment Tree 模板，雖然這題實際上並無需要 lazy 的區間操作，但沿用 template 可
  快速實作。
- `query()` 採用「左優先遞迴」方式找最靠左的符合條件者。
- 為保留原始值，用 `hotel[]` 陣列記錄旅館目前剩餘容量。
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
struct LazySegTree {
    int n;
    vector<long long> tree, lazy;
 
    LazySegTree(int size) {
        n = size;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, -1);
    }
 
    void push(int node, int l, int r) {
        if (lazy[node] != -1) {
            tree[node] = lazy[node];
            if (l != r) {
                lazy[2 * node] = lazy[node];
                lazy[2 * node + 1] = lazy[node];
            }
            lazy[node] = -1;
        }
    }
 
    void update(int node, int l, int r, int ul, int ur, long long val) {
        push(node, l, r);
        if (r < ul || ur < l) return;
        if (ul <= l && r <= ur) {
            lazy[node] = val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ul, ur, val);
        update(2 * node + 1, mid + 1, r, ul, ur, val);
        tree[node] = max(tree[2 * node] , tree[2 * node + 1]);
    }
 
    long long query(int node, int l, int r, int num) {
        push(node, l, r);
        long long mid = (l + r) / 2;
        long long L = LLONG_MAX, R = LLONG_MAX; 
        if(l == r){
            if(tree[node] >= num){
                return mid;
            } else {
                return LLONG_MAX;
            }
        } else if(tree[2 * node] >= num){
            L = query(2 * node, l, mid, num);
        } else if(tree[2 * node + 1] >= num){
            R = query(2 * node + 1, mid + 1, r, num);
        }
        return min(L, R);
    }
 
    // wrapper functions
    void add(int l, int r, long long val) {
        update(1, 0, n - 1, l, r, val);
    }
 
    long long range_query(int num) {
        return query(1, 0, n - 1, num);
    }
};
 
int main(){
    fastio;
    int n, m;
    cin >> n >> m;
    
    vector<int> hotel(n);
    LazySegTree st(n);
 
    for(int i = 0; i < n; ++i){
        int num; cin >> num;
        st.add(i, i, num);
        hotel[i] = num;
    }
 
    while(m--){
        int a;
        cin >> a;
        long long ans = st.range_query(a);
        if(ans != LLONG_MAX){
            st.add(ans, ans, hotel[ans] - a);
            hotel[ans] -= a;
            cout << ans + 1 << ' ';
        } else {
            cout << 0 << ' ';
        }
    }
}
```

## List Removals [problem](https://cses.fi/problemset/task/1749)
```markdown
題目: 

- 給定一個長度為 n 個陣列，每個元素編號為 1 到 n。
- 每次 query 刪掉第 k 個元素，並輸出該元素。
```
``` markdown
解法 : 

### 1. 使用 Segment Tree 解決動態 k-th 人問題
- 我們將所有元素用一個陣列 `element[]` 表示。
- 建立一個 Segment Tree，節點值表示某區間內還活著的元素（即 1 表示該元素還在）。
- 每次要刪除第 k 個元素，可以視為從整體中找第 k 個 1（k-th one），這可以透過 
  Segment Tree 快速達成。
- 找到後將該元素設為 0（標記為已刪除）。

---

### 2. 注意事項
- `range_sum(k)`：在 Segment Tree 中找到前綴和為 k 的最左位置。
- `add(pos, pos, 0)`：將該位置設為 0，代表這個元素已經移除。
- 每回合讀入的 `a` 就是我們要找的第 a 個活元素。
```

``` cpp
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
struct LazySegTree {
    int n;
    vector<long long> tree, lazy;
 
    LazySegTree(int size) {
        n = size;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, -1);
    }
 
    void push(int node, int l, int r) {
        if (lazy[node] != -1) {
            tree[node] = (r - l + 1) * lazy[node];
            if (l != r) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = -1;
        }
    }
 
    void update(int node, int l, int r, int ul, int ur, long long val) {
        push(node, l, r);
        if (r < ul || ur < l) return;
        if (ul <= l && r <= ur) {
            lazy[node] = val;
            push(node, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(2 * node, l, mid, ul, ur, val);
        update(2 * node + 1, mid + 1, r, ul, ur, val);
        tree[node] = (tree[2 * node] + tree[2 * node + 1]);
    }
 
    long long query(int node, int l, int r, int num) {
        push(node, l, r);
        long long mid = (l + r) / 2;
        long long L = LLONG_MAX, R = LLONG_MAX; 
        if(l == r){
            if(tree[node] >= num){
                return l;
            } else {
                return LLONG_MAX;
            }
        } else if(tree[2 * node] >= num){
            L = query(2 * node, l, mid, num);
        } else if(tree[2 * node + 1] >= num - tree[2 * node]){
            R = query(2 * node + 1, mid + 1, r, num - tree[2 * node]);
        }
        return min(L, R);
    }
 
    // wrapper functions
    void add(int l, int r, long long val) {
        update(1, 0, n - 1, l, r, val);
    }
 
    long long range_sum(int num) {
        return query(1, 0, n - 1, num);
    }
};
 
int main(){
    fastio;
    int n, m;
    cin >> n;
    
    LazySegTree st(n);
    vector<long long> element(n);
 
    for(int i = 0; i < n; ++i){
        int num; cin >> num;
        st.add(i, i, 1);
        element[i] = num;
    }
    
    while(n--){
        int a;
        cin >> a;
        long long pos = st.range_sum(a);
        cout << element[pos] << ' ';
        st.add(pos, pos, 0);
    }
}
```

## Salary Queries [problem](https://cses.fi/problemset/task/1144)
```markdown
題目: 

- 有 n 位員工，每人有一份薪水。
- 有 q 筆操作，包含：
  - `! a b`: 將第 a 位員工的薪水更新為 b。
  - `? a b`: 詢問薪資範圍在 [a, b] 之間的員工有多少位。
- 每次查詢都需要快速回應。
```
``` markdown
解法 : 

### 1. 離散化 + Binary Indexed Tree（Fenwick Tree）
- 薪資值範圍過大，需先將所有出現過的薪資值進行離散化。
- 使用 BIT 維護薪資值的出現次數。
- 查詢 [a, b] 轉為 prefix sum 差值：`sum(b_idx) - sum(a_idx - 1)`
- 更新員工薪資時，先從舊值位置 -1，再在新值位置 +1。

---

### 2. 離散化細節
- 收集所有出現過的薪資值（初始 + 所有查詢中的 b）。
- 使用 `lower_bound()` 與 `upper_bound()` 找到對應的區間範圍。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 4e5 + 5;
int BIT[MAXN];
 
void add(int idx, int val) {
    while (idx < MAXN) {
        BIT[idx] += val;
        idx += idx & -idx;
    }
}
 
int sum(int idx) {
    int res = 0;
    while (idx > 0) {
        res += BIT[idx];
        idx -= idx & -idx;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, q;
    cin >> n >> q;
 
    vector<int> p(n + 1);
    vector<pair<char, pair<int, int>>> queries;
    vector<int> all_vals;
 
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        all_vals.push_back(p[i]);
    }
 
    for (int i = 0; i < q; ++i) {
        char type;
        int a, b;
        cin >> type >> a >> b;
        queries.emplace_back(type, make_pair(a, b));
        all_vals.push_back(b); // 不管是 ? 還是 ! 都會用到 b
    }
 
    // 離散化
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
 
    auto get_index = [&](int x) -> int {
        return lower_bound(all_vals.begin(), all_vals.end(), x) - all_vals.begin() + 1;
    };
 
    vector<int> salary_idx(n + 1);
    for (int i = 1; i <= n; ++i) {
        salary_idx[i] = get_index(p[i]);
        add(salary_idx[i], 1);
    }
 
    for (auto &[type, ab] : queries) {
        int a = ab.first, b = ab.second;
        if (type == '!') {
            add(salary_idx[a], -1);
            salary_idx[a] = get_index(b);
            add(salary_idx[a], 1);
        } else {
            if (a > b) {
                cout << "0\n";
                continue;
            }
            int la = lower_bound(all_vals.begin(), all_vals.end(), a) - all_vals.begin() + 1;
            int rb = upper_bound(all_vals.begin(), all_vals.end(), b) - all_vals.begin();
 
            if (la > rb) cout << "0\n";
            else cout << sum(rb) - sum(la - 1) << '\n';
        }
    }
 
    return 0;
}
```

## Prefix Sum Queries [problem](https://cses.fi/problemset/task/2166)
```markdown
題目: 

- 有一個長度為 n 的整數陣列。
- q 筆操作，包含：
  1. `1 i x`：將第 i 個元素設為 x。
  2. `2 l r`：查詢區間 [l, r] 的最大子陣列和。
- 要求高效完成所有操作。
```
``` markdown
解法 : 

### 1. 使用 Prefix Sum + Segment Tree with Lazy Propagation
這題可以只用標準 Segment Tree，但我們沿用更通用的做法：
- 計算 prefix sum 陣列 `prefix[i] = a[1] + ... + a[i]`
- 利用 segment tree 維護區間的 prefix 最大值
- 更新第 i 項時，相當於將第 i~n 區間都進行加法 → 用 **lazy propagation 做 range add**
- 查詢區間最大子段和 `a[l..r]`，即為 `max(prefix[r]) - prefix[l-1]`

---

### 2. 節點資訊
每個節點維護：
- 區間最大值 `max_val`
- 懶標記 `lazy`：表示尚未傳遞的區間加總

查詢時需加上懶標記進行正確比對。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct Node {
    ll sum, prefix, suffix, res;
};

int n, q;
vector<Node> tree;
vector<ll> a;

Node merge(Node l, Node r) {
    Node res;
    res.sum = l.sum + r.sum;
    res.prefix = max(l.prefix, l.sum + r.prefix);
    res.suffix = max(r.suffix, r.sum + l.suffix);
    res.res = max({l.res, r.res, l.suffix + r.prefix});
    return res;
}

void build(int node, int l, int r) {
    if (l == r) {
        ll val = a[l];
        tree[node] = {val, max(0LL, val), max(0LL, val), max(0LL, val)};
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}

void update(int node, int l, int r, int idx, ll val) {
    if (l == r) {
        tree[node] = {val, max(0LL, val), max(0LL, val), max(0LL, val)};
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) update(2 * node, l, mid, idx, val);
    else update(2 * node + 1, mid + 1, r, idx, val);
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}

Node query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return {0, 0, 0, 0};  // neutral element
    if (ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return merge(
        query(2 * node, l, mid, ql, qr),
        query(2 * node + 1, mid + 1, r, ql, qr)
    );
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    a.resize(n + 1);
    tree.resize(4 * (n + 1));

    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);

    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) {
            update(1, 1, n, x, y);
        } else {
            cout << query(1, 1, n, x, y).res << '\n';
        }
    }
}
```

## Pizzeria Queries [problem](https://cses.fi/problemset/task/2206)
```markdown
題目: 

- 有 n 個披薩店，每家店的位置為其在陣列中的編號（0-based）。
- 每家店的披薩價格為 p[i]，但實際價格會因顧客與披薩店的距離產生變化。
- 顧客與披薩店的距離為 |i - k|，所以顧客要付的價格為 p[i] + |i - k|。
- 有兩種操作：
  - `1 k x`：把第 k 家披薩店價格更新為 x
  - `2 k`：查詢顧客在第 k 個位置要花的最小費用。
```
``` markdown
解法 : 

### 1. 把絕對值變成兩個區段討論：
   - 目標是最小化 p[i] + |i - k|。
   - 當 i <= k 時：p[i] + (k - i) = (p[i] - i) + k
   - 當 i >= k 時：p[i] + (i - k) = (p[i] + i) - k
   - 所以可以將原本的 p[i] 轉換成兩個陣列：
     - left[i] = p[i] - i，對應於 i ≤ k
     - right[i] = p[i] + i，對應於 i ≥ k

---

### 2. 建兩棵 Segment Tree：
   - `segL` 用來維護 left[i]，查詢範圍為 [0, k]
   - `segR` 用來維護 right[i]，查詢範圍為 [k, n-1]
   - 每次查詢答案為：
     - `min( segL.query(0, k) + k, segR.query(k, n-1) - k )`

---

### 3. 更新操作：
   - 每次把第 k 家店的價錢改為 x，需要更新：
     - left[k] = x - k
     - right[k] = x + k
   - 分別更新 `segL` 和 `segR`。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
const int INF = 1e18;
 
struct SegmentTree {
    int n;
    vector<int> tree;
 
    SegmentTree(int sz) {
        n = sz;
        tree.assign(4*n, INF);
    }
 
    void build(int idx, int l, int r, const vector<int>& arr) {
        if (l == r) {
            tree[idx] = arr[l];
            return;
        }
        int mid = (l+r)/2;
        build(2*idx, l, mid, arr);
        build(2*idx+1, mid+1, r, arr);
        tree[idx] = min(tree[2*idx], tree[2*idx+1]);
    }
 
    void update(int idx, int l, int r, int pos, int val) {
        if (l == r) {
            tree[idx] = val;
            return;
        }
        int mid = (l+r)/2;
        if (pos <= mid) update(2*idx, l, mid, pos, val);
        else update(2*idx+1, mid+1, r, pos, val);
        tree[idx] = min(tree[2*idx], tree[2*idx+1]);
    }
 
    int query(int idx, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return INF;
        if (ql <= l && r <= qr) return tree[idx];
        int mid = (l+r)/2;
        return min(query(2*idx, l, mid, ql, qr), query(2*idx+1, mid+1, r, ql, qr));
    }
};
 
inline void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
 
int32_t main() {
    fastio();
    int n, q;
    cin >> n >> q;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
 
    vector<int> left(n), right(n);
    for (int i = 0; i < n; ++i) {
        left[i] = p[i] - i;
        right[i] = p[i] + i;
    }
 
    SegmentTree segL(n), segR(n);
    segL.build(1, 0, n-1, left);
    segR.build(1, 0, n-1, right);
 
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int k, x; cin >> k >> x; --k;
            segL.update(1, 0, n-1, k, x-k);
            segR.update(1, 0, n-1, k, x+k);
        } else {
            int k; cin >> k; --k;
            int res = INF;
            res = min(res, segL.query(1, 0, n-1, 0, k) + k);
            res = min(res, segR.query(1, 0, n-1, k, n-1) - k);
            cout << res << '\n';
        }
    }
 
    return 0;
}
```

## Visible Buildings Queries [problem](https://cses.fi/problemset/task/3304)
```markdown
題目: 

- 給定一列建築物的高度 h[1..n]。
- 一個建築物可以「看到」右邊第一個比自己高的建築。
- 給 q 組查詢，每次問從第 a 棟出發，往右最多看到幾棟建築（包括自己），且不能超過第 b 棟。
```
``` markdown
解法 : 

### 1. 預處理每棟樓能看到的下一棟：
   - 用 stack 從右往左掃，維護「右邊第一個比自己高」的建築編號。
   - 記錄為 `nxt[i]`，代表從 i 能跳到哪一棟。

---

### 2. Binary Lifting 加速跳躍：
   - 建立 jump table：jump[k][i] 表示從 i 出發，跳 2^k 次會到哪棟。
   - 初始 jump[0][i] = nxt[i]
   - 遞推 jump[k][i] = jump[k-1][jump[k-1][i]]
   - 預處理時間 O(n log n)

---

### 3. 查詢：
   - 對於每次查詢 (a, b)，從 a 開始跳。
   - 若 jump[k][curr] ≤ b 就可以跳，並累加 (1 << k) 到答案。
   - 每次查詢最多跳 log n 次，時間 O(log n)
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5 + 5;
const int LOG = 20;
 
int n, q;
int h[MAXN]; // height of buildings, 1-based
int nxt[MAXN]; // nxt[i] = next visible building from i
int jump[LOG][MAXN]; // jump[k][i] = from i, jump 2^k steps
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> h[i];
 
    // Step 1: 建 next[]（右邊第一個比它高的建築）
    stack<int> s;
    for (int i = n; i >= 1; --i) {
        while (!s.empty() && h[s.top()] <= h[i]) s.pop();
        if (!s.empty()) nxt[i] = s.top();
        else nxt[i] = n + 1; // 超出界限
        s.push(i);
    }
 
    // Step 2: 建 jump table (binary lifting)
    for (int i = 1; i <= n + 1; ++i)
        jump[0][i] = nxt[i];
    jump[0][n + 1] = n + 1; // 防止越界亂跳
 
    for (int k = 1; k < LOG; ++k)
        for (int i = 1; i <= n + 1; ++i)
            jump[k][i] = jump[k - 1][jump[k - 1][i]];
 
    // Step 3: 處理每個 query
    while (q--) {
        int a, b;
        cin >> a >> b;
        int ans = 1; // 至少看到 a 自己
        int curr = a;
        for (int k = LOG - 1; k >= 0; --k) {
            if (jump[k][curr] <= b) {
                curr = jump[k][curr];
                ans += (1 << k);
            }
        }
        cout << ans << '\n';
    }
}
```

## Range Interval Queries [problem](https://cses.fi/problemset/task/3163)
```markdown
題目: 

- 給定一個長度為 n 的整數陣列 x[1..n]。
- 有 m 個查詢，每次給定範圍 [a, b] 和數值範圍 [c, d]。
- 問在區間 x[a..b] 中，有多少元素的值落在 [c, d] 區間中。
```
``` markdown
解法 : 

### 1. Wavelet Tree：
   - 這類屬於「區間值域查詢」，適合使用 Wavelet Tree。
   - 時間複雜度為 O(log V)，V 為值域大小。
   - 這裡使用座標壓縮將值域壓縮到 0 ~ n-1，避免實際建到 1e9 的空間。

---

### 2. 實作細節：
   - `raw`：將輸入陣列排序後去重，作為值域基準。
   - `encode(val)`：將原始值映射到座標壓縮後的編號。
   - 查詢時將 [c, d] 映射到編號區間 [l, r]。
   - Wavelet Tree 支援查詢區間 [a, b] 內小於等於 k 的數量。
   - 所以答案為 `LTE(a, b, r) - LTE(a, b, l - 1)`。
```

``` cpp
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
struct WaveletTree {
    int lo, hi;
    WaveletTree *l, *r;
    vector<int> b;
 
    WaveletTree(vector<int>::iterator from, vector<int>::iterator to, int x, int y) {
        lo = x, hi = y;
        if (from >= to || lo > hi) return;
 
        if (lo == hi) {
            b.resize(to - from + 1);
            iota(b.begin(), b.end(), 0);
            return;
        }
 
        int mid = (lo + hi) / 2;
        vector<int> left, right;
        b.reserve(to - from + 1);
        b.push_back(0);
        for (auto it = from; it != to; ++it) {
            if (*it <= mid) {
                left.push_back(*it);
                b.push_back(b.back() + 1);
            } else {
                right.push_back(*it);
                b.push_back(b.back());
            }
        }
        l = new WaveletTree(left.begin(), left.end(), lo, mid);
        r = new WaveletTree(right.begin(), right.end(), mid + 1, hi);
    }
 
    int LTE(int lq, int rq, int k) {
        if (lq > rq || k < lo) return 0;
        if (hi <= k) return rq - lq + 1;
        return l->LTE(b[lq - 1] + 1, b[rq], k) +
               r->LTE(lq - b[lq - 1], rq - b[rq], k);
    }
};
 
int main() {
    fastio;
    int n, m;
    cin >> n >> m;
 
    vector<int> x(n), c(m), d(m);
    for (int i = 0; i < n; ++i)
        cin >> x[i];
 
    vector<tuple<int, int, int, int>> queries(m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b >> c[i] >> d[i];
        queries[i] = {a, b, c[i], d[i]};
    }
 
    vector<int> raw(x.begin(), x.end());
    sort(raw.begin(), raw.end());
    raw.erase(unique(raw.begin(), raw.end()), raw.end());
 
    auto encode = [&](int val) {
        return lower_bound(raw.begin(), raw.end(), val) - raw.begin();
    };
 
    vector<int> compressed(n);
    for (int i = 0; i < n; ++i)
        compressed[i] = encode(x[i]);
 
    WaveletTree wt(compressed.begin(), compressed.end(), 0, raw.size() - 1);
 
    for (int i = 0; i < m; ++i) {
        auto [a, b, cc, dd] = queries[i];
        int l = lower_bound(raw.begin(), raw.end(), cc) - raw.begin();
        int r = upper_bound(raw.begin(), raw.end(), dd) - raw.begin() - 1;
 
        if (l >= (int)raw.size() || r < 0 || l > r) {
            cout << 0 << '\n';
            continue;
        }
        l = max(l, 0);
        r = min(r, (int)raw.size() - 1);
        cout << wt.LTE(a, b, r) - wt.LTE(a, b, l - 1) << '\n';
    }
}
```

## Subarray Sum Queries [problem](https://cses.fi/problemset/task/1190)
```markdown
題目: 

- 給定一個長度為 n 的整數陣列。
- 有 m 筆操作：
  1. `1 k x`：將第 k 個數字改為 x。
  2. `2 a b`：查詢區間 [a, b] 中的最大子段和（可以是空子段，最小為 0）。
- 陣列可能包含負數，需快速更新與查詢。
```
``` markdown
解法 : 

### 1. Segment Tree 維護最大子段和（Maximum Subarray Sum）
每個節點維護四個資訊：
- `sum`：整個區間的總和
- `prefix`：區間最大前綴和
- `suffix`：區間最大後綴和
- `best`：區間內最大子段和

這些資訊可在合併左右子樹時維護：
- res.sum    = L.sum + R.sum;
- res.prefix = max(L.prefix, L.sum + R.prefix);
- res.suffix = max(R.suffix, R.sum + L.suffix);
- res.best   = max({L.best, R.best, L.suffix + R.prefix});

---

### 2. 查詢邏輯
- 使用線段樹查詢區間 [l, r] 對應的節點合併結果。
- 若區間內元素皆為負數，返回 0 即為空子段和。
```

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

struct Node {
    long long sum, prefix, suffix, best;
    Node(long long val = 0) {
        sum = prefix = suffix = best = val;
    }
};

const int MAXN = 2e5 + 5;
Node tree[4 * MAXN];
int arr[MAXN];

Node merge(const Node &left, const Node &right) {
    Node res;
    res.sum = left.sum + right.sum;
    res.prefix = max(left.prefix, left.sum + right.prefix);
    res.suffix = max(right.suffix, right.sum + left.suffix);
    res.best = max({left.best, right.best, left.suffix + right.prefix});
    return res;
}

void build(int l, int r, int idx) {
    if (l == r) {
        tree[idx] = Node(arr[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, idx * 2);
    build(mid + 1, r, idx * 2 + 1);
    tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

void update(int pos, int val, int l, int r, int idx) {
    if (l == r) {
        tree[idx] = Node(val);
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(pos, val, l, mid, idx * 2);
    else update(pos, val, mid + 1, r, idx * 2 + 1);
    tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}

Node query(int ql, int qr, int l, int r, int idx) {
    if (qr < l || r < ql) return Node(0); // neutral for sum, best=0
    if (ql <= l && r <= qr) return tree[idx];
    int mid = (l + r) / 2;
    Node left = query(ql, qr, l, mid, idx * 2);
    Node right = query(ql, qr, mid + 1, r, idx * 2 + 1);
    return merge(left, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    build(1, n, 1);

    while (m--) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            update(a, b, 1, n, 1);
        } else {
            cout << max(0LL, query(a, b, 1, n, 1).best) << '\n';
        }
    }

    return 0;
}
```

## Subarray Sum Queries II [problem](https://cses.fi/problemset/task/3226)
```markdown
題目: 

- 給定長度為 n 的整數陣列 a[1..n]。
- 有 m 次查詢，每次輸入區間 [a, b]，輸出該區間的最大子陣列和（最大連續子區間和）。
- 若區間內所有數都為負數，則輸出 0。
```
``` markdown
解法 : 

### 1. 使用 Segment Tree 儲存區間資訊：
   - 每個節點維護四個值：
     - `sum`: 區間總和
     - `prefix`: 從左邊開始的最大前綴和
     - `suffix`: 從右邊開始的最大後綴和
     - `best`: 該區間的最大子陣列和

---

### 2. 合併邏輯（Merge）：
   - `sum = L.sum + R.sum`
   - `prefix = max(L.prefix, L.sum + R.prefix)`
   - `suffix = max(R.suffix, R.sum + L.suffix)`
   - `best = max(L.best, R.best, L.suffix + R.prefix)`
   - 類似於線段樹版本的 Kadane's Algorithm
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
struct Node {
    long long sum, prefix, suffix, best;
    Node(long long val = 0) {
        sum = prefix = suffix = best = val;
    }
};
 
const int MAXN = 2e5 + 5;
Node tree[4 * MAXN];
int arr[MAXN];
 
Node merge(const Node &left, const Node &right) {
    Node res;
    res.sum = left.sum + right.sum;
    res.prefix = max(left.prefix, left.sum + right.prefix);
    res.suffix = max(right.suffix, right.sum + left.suffix);
    res.best = max({left.best, right.best, left.suffix + right.prefix});
    return res;
}
 
void build(int l, int r, int idx) {
    if (l == r) {
        tree[idx] = Node(arr[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, idx * 2);
    build(mid + 1, r, idx * 2 + 1);
    tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}
 
void update(int pos, int val, int l, int r, int idx) {
    if (l == r) {
        tree[idx] = Node(val);
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(pos, val, l, mid, idx * 2);
    else update(pos, val, mid + 1, r, idx * 2 + 1);
    tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}
 
Node query(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return 0;
    if (ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return merge(query(2 * node, l, mid, ql, qr)
            , query(2 * node + 1, mid + 1, r, ql, qr));
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    build(1, n, 1);
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << max(0LL, query(1, 1, n, a, b).best) << '\n'; // 最大子陣列和（若全負則輸出 0）
    }
 
    return 0;
}
```

## Distinct Values Queries [problem](https://cses.fi/problemset/task/1734)
```markdown
題目: 

- 給定一個長度為 n 的整數陣列 a[1..n]。
- 有 q 組查詢，每次給定區間 [l, r]，問該區間中有多少個「不同」的數值（distinct elements）。
```
``` markdown
解法 : 


### 1. Mo's Algorithm（離線區間查詢技巧）：
   - 適合處理所有查詢都已知，並且查詢不需要修改值的情況。
   - 將所有查詢依據 block 編號與右端點排序，可保證單次移動成本 amortized 為 O(√n)。
   - 每筆查詢以滑動窗口的方式維護當前區間 [curr_l, curr_r] 的答案。
   - 本題的答案是當前區間中有多少個不同的元素（可以用 `frequency[x] == 1` 來判斷）。

---

### 2. 離散化（Coordinate Compression）：
   - 由於 a[i] 數值可能過大（最多 1e9），須先離散化。
   - 排序 + 去重後將所有值映射為 1 ~ n 範圍內的編號，方便開 frequency 陣列。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
 
int n, q, block_size;
int A[N], ans[N];
struct Query {
    int l, r, idx;
    bool operator<(const Query& other) const {
        if (l / block_size != other.l / block_size)
            return l / block_size < other.l / block_size;
        return r < other.r; 
    }
};
 
vector<Query> queries;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    block_size = sqrt(n);
 
    vector<int> raw(n+1);
    for (int i = 1; i <= n; ++i) cin >> raw[i];
 
    // 離散化
    vector<int> tmp = raw;
    sort(tmp.begin() + 1, tmp.end());
    tmp.erase(unique(tmp.begin() + 1, tmp.end()), tmp.end());
    for (int i = 1; i <= n; ++i) {
        A[i] = lower_bound(tmp.begin() + 1, tmp.end(), raw[i]) - tmp.begin();
    }
 
    for (int i = 0; i < q; ++i) {
        int l, r; cin >> l >> r;
        queries.push_back({l, r, i});
    }
 
    sort(queries.begin(), queries.end());
 
    vector<int> freq(n+2, 0); // 離散化後最多 n
    int distinct = 0;
 
    auto add = [&](int pos) {
        if (++freq[A[pos]] == 1) distinct++;
    };
    auto remove = [&](int pos) {
        if (--freq[A[pos]] == 0) distinct--;
    };
 
    int curr_l = 1, curr_r = 0;
    for (auto& query : queries) {
        int l = query.l, r = query.r;
 
        while (curr_l > l) add(--curr_l);
        while (curr_r < r) add(++curr_r);
        while (curr_l < l) remove(curr_l++);
        while (curr_r > r) remove(curr_r--);
 
        ans[query.idx] = distinct;
    }
 
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
 
    return 0;
}
```

## Distinct Values Queries II [problem](https://cses.fi/problemset/task/3356)
```markdown
題目: 

- 給定長度為 n 的陣列 A[1..n]，初始為整數。
- 有兩種操作：
  - `1 pos val`：把第 pos 個位置更新為 val。
  - `2 l r`：詢問區間 A[l..r] 是否所有值皆互不相同（distinct）？
- 回答 YES 或 NO。
```
``` markdown
解法 : 

### 1. 觀察目標：
   - 如果區間 [l, r] 中有兩個位置值相同，則這區間「不是全 distinct」。
   - 問題轉化為：是否存在某個 i ∈ [l, r] 使得「i 的下一個出現位置」在 [l, r] 內？

---

### 2. 使用 S[i] 表示下一次出現的位置：
   - 若 i 是某值的前一次出現，則 S[i] 記錄下一次出現的位置。
   - 若某個 S[i] ∈ [l, r]，則區間內存在重複 → 輸出 NO。
   - 否則輸出 YES。

---

### 3. Segment Tree 維護最小 S[i]：
   - 建一棵 Segment Tree，維護每個位置的 S[i]。
   - 對於每次查詢 (l, r)，查詢區間最小值 minS = min{S[l..r]}。
   - 若 minS ≤ r，代表區間內有重複元素。

---

### 4. 動態更新：
   - 使用 `map<int, set<int>>` 記錄每個值的位置集合。
   - 每次值更新，調整相鄰出現位置的 S[] 並用 Segment Tree 更新。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e9+10;
 
struct SegmentTree {
    int n;
    vector<int> tree;
 
    SegmentTree(int sz) {
        n = sz;
        tree.assign(4*n, INF);
    }
 
    void build(int idx, int l, int r, const vector<int>& S) {
        if (l == r) {
            tree[idx] = S[l];
            return;
        }
        int mid = (l+r)/2;
        build(2*idx, l, mid, S);
        build(2*idx+1, mid+1, r, S);
        tree[idx] = min(tree[2*idx], tree[2*idx+1]);
    }
 
    void update(int idx, int l, int r, int pos, int val) {
        if (l == r) {
            tree[idx] = val;
            return;
        }
        int mid = (l+r)/2;
        if (pos <= mid) update(2*idx, l, mid, pos, val);
        else update(2*idx+1, mid+1, r, pos, val);
        tree[idx] = min(tree[2*idx], tree[2*idx+1]);
    }
 
    int query(int idx, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return INF;
        if (ql <= l && r <= qr) return tree[idx];
        int mid = (l+r)/2;
        return min(query(2*idx, l, mid, ql, qr), query(2*idx+1, mid+1, r, ql, qr));
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
    vector<int> A(n+1);
    for (int i = 1; i <= n; ++i) cin >> A[i];
 
    vector<int> S(n+1, INF);
    map<int, set<int>> pos_map;
 
    for (int i = 1; i <= n; ++i) {
        auto& s = pos_map[A[i]];
        if (!s.empty()) {
            int prv = *prev(s.end());
            S[prv] = i;
        }
        s.insert(i);
    }
 
    SegmentTree seg(n+1);
    seg.build(1,1,n,S);
 
    while (q--) {
        int type;
        cin >> type;
        if (type == 2) {
            int l, r;
            cin >> l >> r;
            int minS = seg.query(1,1,n,l,r);
            cout << (minS <= r ? "NO\n" : "YES\n");
        } else {
            int pos, val;
            cin >> pos >> val;
            if (A[pos] == val) continue;
 
            // 刪除舊值鏈上的 pos
            {
                auto& s = pos_map[A[pos]];
                auto it = s.find(pos);
                int prv = -1, nxt = -1;
 
                if (it != s.begin()) prv = *prev(it);
                if (next(it) != s.end()) nxt = *next(it);
 
                if (prv != -1) {
                    S[prv] = nxt == -1 ? INF : nxt;
                    seg.update(1,1,n,prv,S[prv]);
                }
                if (nxt != -1) {
                    // 不需要處理 S[nxt] 因為它已經指向它之後的
                }
 
                S[pos] = INF;
                seg.update(1,1,n,pos,INF);
                s.erase(it);
            }
 
            A[pos] = val;
 
            // 插入新值鏈上的 pos
            {
                auto& s = pos_map[val];
                s.insert(pos);
                auto it = s.find(pos);
                int prv = -1, nxt = -1;
 
                if (it != s.begin()) prv = *prev(it);
                if (next(it) != s.end()) nxt = *next(it);
 
                if (prv != -1) {
                    S[prv] = pos;
                    seg.update(1,1,n,prv,S[prv]);
                }
 
                if (nxt != -1) {
                    S[pos] = nxt;
                } else {
                    S[pos] = INF;
                }
                seg.update(1,1,n,pos,S[pos]);
            }
        }
    }
    return 0;
}
```

## Increasing Array Queries [problem](https://cses.fi/problemset/task/2416)
```markdown
題目: 

- 給定一個長度為 n 的陣列 a[1..n]。
- 定義你可以執行以下操作任意次：
  - 選定一個區間 [l..r]，把 a[l..r] 區間內的所有值設為同一個值 v（只要這樣做不會讓陣列不遞增）。
- 現在有 q 個查詢，每個查詢給你一個區間 [l, r]，問若從原始 a[] 依序進行操作直到整個陣列遞增後，
  a[l..r] 的總和會是多少。
```
``` markdown
解法 : 

### 1. 模擬「變成遞增陣列」的過程：
   - 要讓陣列遞增，當 a[i] < a[i-1] 時，就需要把 a[i] 提高到 a[i-1]。
   - 所以我們可以倒著從右往左處理，維持一個「單調不遞減」的序列。
   - 對每個位置 l，我們會把區間 [l, r] 設為 a[l]，其中 r 是第一個滿足 a[r] ≥ a[l] 的位置。

---

### 2. Segment Tree 維護目前陣列：
   - 使用一棵 Lazy Segment Tree：
     - 支援區間 assign：將一段區間全部設為某個值。
     - 支援區間最大值查詢 mx[]
     - 支援區間總和查詢 sm[]
   - 還需要一個 `orderOf()` 函數，找出從某個位置 l 開始，第一個比 a[l] 小的位置，作為 assign 
     的右邊界。

---

### 3. 處理查詢：
   - 使用前綴和 a[i] → 原始總和為 a[r] - a[l-1]
   - 更新後總和使用 Segment Tree 查詢 sum(l, r)
   - 所以答案為：
     - `sum(l, r) - (a[r] - a[l-1])`，表示總共補上去的值（花費）
```

``` cpp
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxN = 2e5+1;
const int SIZE = 4*maxN;
 
int N, Q, lo[SIZE], hi[SIZE];
ll a[maxN], ass[SIZE], mx[SIZE], sm[SIZE], ans[maxN];
vector<pii> queries[maxN];
 
int len(int i){
    return hi[i]-lo[i]+1;
}
 
void assign(int i, ll val){
    ass[i] = mx[i] = val;
    sm[i] = val * len(i);
}
 
void push(int i){
    if(ass[i]){
        assign(2*i, ass[i]);
        assign(2*i+1, ass[i]);
        ass[i] = 0;
    }
}
 
void pull(int i){
    sm[i] = sm[2*i] + sm[2*i+1];
    mx[i] = max(mx[2*i], mx[2*i+1]);
}
 
void init(int i, int l, int r){
    lo[i] = l; hi[i] = r;
    if(l == r){
        sm[i] = a[l];
        return;
    }
    int m = (l+r)/2;
    init(2*i, l, m);
    init(2*i+1, m+1, r);
    pull(i);
}
 
void update(int i, int l, int r, ll val){
    if(l > hi[i] || r < lo[i])  return;
    if(l <= lo[i] && hi[i] <= r){
        assign(i, val);
        return;
    }
 
    push(i);
    update(2*i, l, r, val);
    update(2*i+1, l, r, val);
    pull(i);
}
 
int orderOf(int i, int l, int val){
    if(lo[i] == hi[i])                  return lo[i];
    push(i);
    int idx = -1;
    if(hi[2*i] <= l || mx[2*i] < val)   idx = orderOf(2*i+1, l, val);
    else                                idx = orderOf(2*i, l, val);
    pull(i);
    return idx;
}
 
ll sum(int i, int l, int r){
    if(l > hi[i] || r < lo[i])      return 0;
    if(l <= lo[i] && hi[i] <= r)    return sm[i];
 
    push(i);
    ll left = sum(2*i, l, r);
    ll right = sum(2*i+1, l, r);
    pull(i);
 
    return left+right;
}
 
int main(){
    scanf("%d %d", &N, &Q);
    for(int i = 1; i <= N; i++)
        scanf("%lld", &a[i]);
 
    init(1, 1, N);
    for(int q = 0, l, r; q < Q; q++){
        scanf("%d %d", &l, &r);
        queries[l].push_back({r, q});
    }
 
    for(int i = 2; i <= N; i++) a[i] += a[i-1];
    for(int l = N; l >= 1; l--){
        int val = a[l]-a[l-1];
        int modifyR = (mx[1] < val ? N+1 : orderOf(1, l, val));
        update(1, l, modifyR-1, val);
        for(pii q : queries[l]){
            int r = q.first;
            int id = q.second;
            ans[id] = sum(1, l, r) - (a[r]-a[l-1]);
        }
    }
 
    for(int i = 0; i < Q; i++)
        printf("%lld\n", ans[i]);
}
```

## Movie Festival Queries

## Forest Queries II [problem](https://cses.fi/problemset/task/1739)
```markdown
題目: 

- 給定一個 n × n 的地圖（1 ≤ n ≤ 1000），由 '.' 和 '*' 組成，代表空地和樹。
- 有 q 次操作，每次為下列兩種之一：
  - `1 y x`：將格子 (y,x) 的內容在 '.' 與 '*' 間切換。
  - `2 y1 x1 y2 x2`：詢問矩形區域內總共有幾棵樹（即 '*' 的個數）。
```
``` markdown
解法 : 

### 1. 使用 2D BIT（Binary Indexed Tree）：
   - 因為有大量查詢與修改，使用 2D Fenwick Tree 來維護每個位置是否有樹。
   - 每次修改對應位置的值 +1 或 -1。
   - 查詢某個矩形區域樹木總數，可以用 2D 前綴和計算：

     ```
     query(y1,x1,y2,x2) = sum(y2,x2) 
                        - sum(y1-1,x2) 
                        - sum(y2,x1-1) 
                        + sum(y1-1,x1-1)
     ```

---

### 2. 初始化：
   - 將初始地圖上所有 '*' 的位置，在 BIT 中加 1。

---

### 3. 更新操作：
   - 若原本為 '*'，則變為 '.' 並從 BIT 扣除 1。
   - 反之則變為 '*' 並在 BIT 加上 1。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1005;
 
int n, q;
int BIT[N][N];
char grid[N][N];
 
// 單點修改 BIT
void add(int x, int y, int delta) {
    for (int i = x; i <= n; i += i & -i) {
        for (int j = y; j <= n; j += j & -j) {
            BIT[i][j] += delta;
        }
    }
}
 
// 查詢 (1,1) ~ (x,y) 的總和
int sum(int x, int y) {
    int res = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            res += BIT[i][j];
        }
    }
    return res;
}
 
// 查詢任意矩形 (y1,x1) ~ (y2,x2)
int query(int y1, int x1, int y2, int x2) {
    return sum(y2, x2) - sum(y1 - 1, x2) - sum(y2, x1 - 1) + sum(y1 - 1, x1 - 1);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        for (int j = 1; j <= n; ++j) {
            grid[i][j] = s[j-1];
            if (grid[i][j] == '*') add(i, j, 1);
        }
    }
 
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int y, x;
            cin >> y >> x;
            if (grid[y][x] == '*') {
                grid[y][x] = '.';
                add(y, x, -1);
            } else {
                grid[y][x] = '*';
                add(y, x, 1);
            }
        } else {
            int y1, x1, y2, x2;
            cin >> y1 >> x1 >> y2 >> x2;
            cout << query(y1, x1, y2, x2) << "\n";
        }
    }
}
```

## Range Updates and Sums [problem](https://cses.fi/problemset/task/1735)
```markdown
題目: 

- 給定長度為 n 的整數陣列 a[1..n]，有 q 次操作，每次為以下三種之一：
  - `1 a b x`：將區間 [a, b] 中的每個元素都加上 x。
  - `2 a b x`：將區間 [a, b] 中的每個元素都設為 x。
  - `3 a b`：詢問區間 [a, b] 的總和。
```
``` markdown
解法 : 

### 1. 使用 Lazy Segment Tree 同時支援加法與指派：
   - 每個節點紀錄：
     - `sum`：該區間總和
     - `add`：延遲加法操作（區間加法用）
     - `set` + `to_set`：延遲指派操作（區間設值用）

---

### 2. 推進與合併邏輯：
   - `push()`：
     - 若該區間被標記為 set，則直接覆蓋子節點並清除加法。
     - 若有 add，則將加法往子節點下推。
   - `range_add()`：
     - 若完全覆蓋，直接加上值並打上 add 標記。
   - `range_set()`：
     - 若完全覆蓋，直接設為該值並打上 set 標記，清除 add。
   - `query()`：
     - 查詢區間和時，需先 push 確保所有延遲標記被處理。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
const int N = 2e5+5;
 
struct Node {
    ll sum, add, set;
    bool to_set;
} seg[N<<2];
 
ll a[N];
int n, q;
 
void build(int id, int l, int r) {
    if (l == r) {
        seg[id].sum = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    seg[id].sum = seg[id*2].sum + seg[id*2+1].sum;
}
 
void push(int id, int l, int r) {
    int mid = (l+r)/2;
    if (seg[id].to_set) {
        ll v = seg[id].set;
        seg[id*2].sum = (mid-l+1)*v;
        seg[id*2+1].sum = (r-mid)*v;
 
        seg[id*2].set = seg[id*2+1].set = v;
        seg[id*2].to_set = seg[id*2+1].to_set = 1;
 
        seg[id*2].add = seg[id*2+1].add = 0;
        seg[id].to_set = 0;
    }
 
    if (seg[id].add) {
        ll v = seg[id].add;
        seg[id*2].sum += (mid-l+1)*v;
        seg[id*2+1].sum += (r-mid)*v;
 
        if (seg[id*2].to_set) seg[id*2].set += v;
        else seg[id*2].add += v;
 
        if (seg[id*2+1].to_set) seg[id*2+1].set += v;
        else seg[id*2+1].add += v;
 
        seg[id].add = 0;
    }
}
 
void range_add(int id, int l, int r, int ql, int qr, ll v) {
    if (ql<=l && r<=qr) {
        seg[id].sum += (r-l+1)*v;
        if (seg[id].to_set) seg[id].set += v;
        else seg[id].add += v;
        return;
    }
    push(id,l,r);
    int mid = (l+r)/2;
    if (ql<=mid) range_add(id*2,l,mid,ql,qr,v);
    if (qr>mid) range_add(id*2+1,mid+1,r,ql,qr,v);
    seg[id].sum = seg[id*2].sum + seg[id*2+1].sum;
}
 
void range_set(int id, int l, int r, int ql, int qr, ll v) {
    if (ql<=l && r<=qr) {
        seg[id].sum = (r-l+1)*v;
        seg[id].set = v;
        seg[id].to_set = 1;
        seg[id].add = 0;
        return;
    }
    push(id,l,r);
    int mid = (l+r)/2;
    if (ql<=mid) range_set(id*2,l,mid,ql,qr,v);
    if (qr>mid) range_set(id*2+1,mid+1,r,ql,qr,v);
    seg[id].sum = seg[id*2].sum + seg[id*2+1].sum;
}
 
ll query(int id, int l, int r, int ql, int qr) {
    if (ql<=l && r<=qr) return seg[id].sum;
    push(id,l,r);
    int mid = (l+r)/2;
    ll res = 0;
    if (ql<=mid) res += query(id*2,l,mid,ql,qr);
    if (qr>mid) res += query(id*2+1,mid+1,r,ql,qr);
    return res;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
 
    cin >> n >> q;
    for (int i=1;i<=n;++i) cin >> a[i];
 
    build(1,1,n);
 
    while (q--) {
        int type,a,b;
        ll x;
        cin >> type >> a >> b;
        if (type==1) {
            cin >> x;
            range_add(1,1,n,a,b,x);
        } else if (type==2) {
            cin >> x;
            range_set(1,1,n,a,b,x);
        } else {
            cout << query(1,1,n,a,b) << "\n";
        }
    }
    return 0;
}
```

## Polynomial Queries [problem](https://cses.fi/problemset/task/1736)
```markdown
題目: 

- 給定長度為 n 的整數陣列 a[1..n]。
- 有 q 個操作，每次為以下兩種之一：
  - `1 l r`：對區間 [l, r] 做如下操作：
    - a[l] += 1, a[l+1] += 2, ..., a[r] += (r - l + 1)
  - `2 l r`：詢問區間 [l, r] 的總和。
```
``` markdown
解法 : 

### 1. 把操作視為等差數列加法：
   - 每次更新相當於往區間 [l, r] 加上一個首項為 1、公差為 1 的等差數列。
   - 可以推廣成加任意首項為 s、公差為 d 的等差級數。

---

### 2. 延遲標記處理兩個變數（s, d）：
   - 使用 Lazy Segment Tree，每個節點標記：
     - `lazy_start`: 延遲加的首項
     - `lazy_d`: 延遲加的公差
   - 使用 `calc(len, s, d)` 計算區間長度為 len 的等差數列總和：
     - `s + (s+d) + ... + (s+(len-1)d)` = `s * len + d * len*(len-1)/2`

---

### 3. 推進 lazy 時要調整首項：
   - 對於左子區間，首項不變。
   - 對於右子區間，首項 = 父首項 + 公差 × 左子長度。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 2e5 + 5;
 
struct Node {
    ll sum = 0;
    ll lazy_start = 0, lazy_d = 0;
} seg[N*4];
 
int n, q;
ll a[N];
 
void build(int i, int l, int r) {
    if (l == r) {
        seg[i].sum = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(i*2, l, m);
    build(i*2+1, m+1, r);
    seg[i].sum = seg[i*2].sum + seg[i*2+1].sum;
}
 
ll calc(int len, ll s, ll d) {
    return s * len + d * 1LL * len * (len-1) / 2;
}
 
void apply(int i, int l, int r, ll s, ll d) {
    seg[i].sum += calc(r-l+1, s, d);
    seg[i].lazy_start += s;
    seg[i].lazy_d += d;
}
 
void push(int i, int l, int r) {
    if (seg[i].lazy_start == 0 && seg[i].lazy_d == 0) return;
 
    int m = (l + r) / 2;
    int left_len = m - l + 1;
 
    // 左兒子：首項 = 父首項，公差不變
    apply(i*2, l, m, seg[i].lazy_start, seg[i].lazy_d);
 
    // 右兒子：首項 = 父首項 + 左兒子長度*公差
    apply(i*2+1, m+1, r, seg[i].lazy_start + seg[i].lazy_d * left_len, seg[i].lazy_d);
 
    seg[i].lazy_start = seg[i].lazy_d = 0;
}
 
void update(int i, int l, int r, int ql, int qr, ll s, ll d) {
    if (qr < l || ql > r) return;
    if (ql <= l && r <= qr) {
        ll start = s + (l - ql) * d;
        apply(i, l, r, start, d);
        return;
    }
    push(i, l, r);
    int m = (l + r) / 2;
    update(i*2, l, m, ql, qr, s, d);
    update(i*2+1, m+1, r, ql, qr, s, d);
    seg[i].sum = seg[i*2].sum + seg[i*2+1].sum;
}
 
ll query(int i, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return seg[i].sum;
    push(i, l, r);
    int m = (l + r) / 2;
    return query(i*2, l, m, ql, qr) + query(i*2+1, m+1, r, ql, qr);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    build(1, 1, n);
 
    while (q--) {
        int type, l, r;
        cin >> type >> l >> r;
 
        if (type == 1) {
            update(1, 1, n, l, r, 1, 1);
        } else {
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
}
```

## Range Queries and Copies [problem](https://cses.fi/problemset/task/1737)
```markdown
題目: 

- 給定長度為 n 的陣列 a[1..n]。
- 有 q 次操作，共三種類型：
  1. `1 k a x`：對第 k 版本的陣列進行修改，將第 a 個位置設為 x。
  2. `2 k a b`：查詢第 k 版本陣列中區間 [a, b] 的總和。
  3. `3 k`：複製第 k 版本陣列，產生一個新的版本（為新的根）。
- 最初的版本為第 0 個版本。
```
``` markdown
解法 : 

### 1. 使用 Persistent Segment Tree（可持久化線段樹）：
   - 每次修改或複製，都產生一棵新樹（實際上僅複製 O(log n) 個節點）
   - 修改操作的時間與空間複雜度皆為 O(log n)
   - 版本透過指針記錄在 `roots[]` 中，每次產生新版本就推入新 root。

---

### 2. 操作說明：
   - `build()`：建構初始線段樹，儲存第 0 版本。
   - `update()`：從某個舊版本 root 出發，僅建立必要的新節點產生新版本。
   - `query()`：在指定版本的 root 上查詢區間和。
   - `copy()`：直接複製 root 指針，空間 O(1)，無需實際複製整棵樹。
```

``` cpp
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAXN = 2e5 + 5;
const int MAXQ = 2e5 + 5;
const int MAXLOG = 20;  // log2(MAXN)
 
struct Node {
    ll sum;
    Node *left, *right;
    Node(ll s = 0) : sum(s), left(nullptr), right(nullptr) {}
};
 
int n, q;
ll arr[MAXN];
vector<Node*> roots;
 
// 建樹
Node* build(int l, int r) {
    Node* node = new Node();
    if (l == r) {
        node->sum = arr[l];
        return node;
    }
    int m = (l + r) / 2;
    node->left = build(l, m);
    node->right = build(m+1, r);
    node->sum = node->left->sum + node->right->sum;
    return node;
}
 
// 更新
Node* update(Node* prev, int l, int r, int pos, ll val) {
    Node* node = new Node();
    if (l == r) {
        node->sum = val;
        return node;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
        node->left = update(prev->left, l, m, pos, val);
        node->right = prev->right;
    } else {
        node->left = prev->left;
        node->right = update(prev->right, m+1, r, pos, val);
    }
    node->sum = node->left->sum + node->right->sum;
    return node;
}
 
// 查詢
ll query(Node* node, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return node->sum;
    int m = (l + r) / 2;
    return query(node->left, l, m, ql, qr) +
           query(node->right, m+1, r, ql, qr);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    roots.push_back(build(1, n));
 
    while (q--) {
        int type;
        cin >> type;
 
        if (type == 1) {
            int k, a, x;
            cin >> k >> a >> x;
            k--;  // 0-based
            roots[k] = update(roots[k], 1, n, a, x);
        } 
        else if (type == 2) {
            int k, a, b;
            cin >> k >> a >> b;
            k--;
            cout << query(roots[k], 1, n, a, b) << "\n";
        } 
        else if (type == 3) {
            int k;
            cin >> k;
            k--;
            roots.push_back(roots[k]);  // 複製指針即可
        }
    }
}
```

## Missing Coin Sum Queries