# 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
Sign in with Wallet
Connect another wallet