Bài 31: Cây Fenwick (BIT) và cây phân đoạn (Segment Tree) trong C++ và Python: truy vấn đoạn có cập nhật
Lời mở đầu
Ở bài 13 em đã biết mảng cộng dồn: tính trước một lần, sau đó hỏi tổng đoạn nào cũng ra ngay trong $O(1)$. Nhưng chỉ cần đề bài thêm một dòng “có thao tác thay đổi giá trị một phần tử” là mảng cộng dồn sụp đổ: mỗi lần sửa phải tính lại cả mảng. Loại bài “vừa cập nhật vừa truy vấn đoạn” xuất hiện rất dày trong đề HSG cấp tỉnh và thi chuyên Tin, nên hôm nay ta học hai “vũ khí” chuyên trị nó.
Cây Fenwick (còn gọi là BIT, Binary Indexed Tree) chỉ dài chục dòng code, dựa trên đúng phép toán bit x & -x em đã gặp ở bài 20. Cây phân đoạn (Segment Tree) dài hơn một chút nhưng làm được nhiều việc hơn hẳn: min, max, tổng, và cả cộng nguyên một đoạn. Ta cũng sẽ giải lại bài đếm nghịch thế của bài 24 theo một cách hoàn toàn khác.
lowbit(i) = i & -i, ô bit[i] quản lý đoạn nào, hai hàm update/query chỉ vài dòng; ứng dụng Fenwick để đếm nghịch thế (kèm nén giá trị) và cộng đoạn, hỏi điểm bằng mảng hiệu; cây phân đoạn: dựng cây, truy vấn ba trường hợp, cập nhật điểm, cài trên mảng $4n$; giới thiệu lazy propagation cho bài cộng đoạn, hỏi tổng đoạn; bảng so sánh để chọn đúng công cụ. Có khung chạy tay Fenwick và cây phân đoạn, ba mô phỏng trực quan và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Bài toán: cập nhật một phần tử, hỏi tổng một đoạn
Cho dãy $a_1, a_2, \ldots, a_n$ và $q$ thao tác, mỗi thao tác thuộc một trong hai loại:
1 i x: cộng $x$ vào $a_i$ (cập nhật điểm);2 l r: in ra $a_l + a_{l+1} + \cdots + a_r$ (truy vấn đoạn).
Với $n, q \le 2 \cdot 10^5$. Hai cách quen thuộc đều có một thao tác “đắt”:
| Cách làm | Cập nhật $a_i$ | Hỏi tổng đoạn | Tệ nhất với $n = q = 2 \cdot 10^5$ |
|---|---|---|---|
| Mảng thường | $O(1)$ | $O(n)$: cộng từng số | $4 \cdot 10^{10}$ phép tính |
| Mảng cộng dồn (bài 13) | $O(n)$: sửa mọi $P_j$ với $j \ge i$ | $O(1)$: $P_r - P_{l-1}$ | $4 \cdot 10^{10}$ phép tính |
| Fenwick / cây phân đoạn | $O(\log n)$ | $O(\log n)$ | khoảng $7 \cdot 10^6$ phép tính |
Bảng 1. Mảng thường “rẻ khi sửa, đắt khi hỏi”, mảng cộng dồn thì ngược lại. Ta cần một cách cân bằng: cả hai thao tác đều $O(\log n)$.
Ý tưởng chung của cả hai cấu trúc: thay vì lưu tổng của mọi tiền tố (sửa một số là kéo theo cả nghìn tiền tố) hay chỉ lưu từng phần tử (hỏi là phải cộng cả nghìn số), ta lưu tổng của một số đoạn được chọn khéo, sao cho:
- mỗi phần tử chỉ thuộc khoảng $\log n$ đoạn → cập nhật chỉ sửa $\log n$ ô;
- mọi đoạn cần hỏi đều ghép được từ khoảng $\log n$ đoạn đã lưu → truy vấn chỉ cộng $\log n$ ô.
Fenwick chọn các đoạn dựa vào biểu diễn nhị phân của chỉ số, còn cây phân đoạn chọn các đoạn bằng cách chia đôi liên tục (giống merge sort ở bài 24).
Phần 2Cây Fenwick (Binary Indexed Tree)
lowbit. Với số nguyên dương $i$, gọi $\text{lowbit}(i)$ là giá trị của bit 1 thấp nhất trong biểu diễn nhị phân của $i$. Ví dụ $6 = 110_2$ có lowbit bằng $2$, $12 = 1100_2$ có lowbit bằng $4$, số lẻ có lowbit bằng $1$. Như đã học ở bài 20, máy tính lưu số âm theo dạng bù 2: $-i$ = (đảo mọi bit của $i$) + 1, nên $i$ và $-i$ chỉ trùng nhau đúng ở bit 1 thấp nhất. Vì vậy:
$\text{lowbit}(i) = i \;\&\; (-i)$. Ví dụ: $12 = 01100_2$, $-12 = 10100_2$ (5 bit thấp), $12 \;\&\; (-12) = 00100_2 = 4$.
Ô bit[i] quản lý đoạn nào? Cây Fenwick là một mảng bit[1..n], trong đó
$\text{bit}[i] = a_{i - \text{lowbit}(i) + 1} + \cdots + a_i$, tức tổng đoạn $(i - \text{lowbit}(i),\, i]$.
Ô lẻ chỉ giữ chính nó, ô $2, 6, 10$ giữ 2 phần tử, ô $4, 12$ giữ 4 phần tử, ô $8$ giữ 8 phần tử… Hình dưới vẽ mỗi ô thành một thanh kết thúc tại cột $i$ và dài đúng $\text{lowbit}(i)$:
| $i$ | nhị phân | lowbit | bit[i] quản lý |
|---|---|---|---|
| 1 | 0001 | 1 | a[1] |
| 2 | 0010 | 2 | a[1..2] |
| 3 | 0011 | 1 | a[3] |
| 4 | 0100 | 4 | a[1..4] |
| 5 | 0101 | 1 | a[5] |
| 6 | 0110 | 2 | a[5..6] |
| 7 | 0111 | 1 | a[7] |
| 8 | 1000 | 8 | a[1..8] |
Bảng 2. Các ô của cây Fenwick 8 phần tử. Đoạn của ô $i$ luôn kết thúc tại $i$ và có độ dài bằng lowbit$(i)$.
Hình 1. Cây Fenwick của dãy a = [5, 2, 9, −3, 5, 20, 10, −5]. Ví dụ t[6] = a[5] + a[6] = 25, t[8] = tổng cả 8 số = 43.
Hỏi tổng tiền tố $a_1 + \cdots + a_i$: lấy bit[i] (đoạn $(i - \text{lowbit}(i), i]$), rồi phần còn lại là tiền tố $a_1..a_{i - \text{lowbit}(i)}$, nên gán $i \mathrel{-}= \text{lowbit}(i)$ và lặp tới khi $i = 0$. Ví dụ $i = 7 = 111_2$: cộng bit[7] (đoạn 7..7), bit[6] (đoạn 5..6), bit[4] (đoạn 1..4). Ba thanh nối liền nhau phủ kín 1..7. Mỗi bước xoá một bit 1 của $i$, nên số bước không quá số bit, tức $\le \log_2 n + 1$.
Cập nhật $a_i \mathrel{+}= x$: phải sửa mọi ô có đoạn chứa $i$. Ô đầu tiên là chính bit[i]; ô kế tiếp phủ lên $i$ là ô $i + \text{lowbit}(i)$ (thanh dài gấp đôi ngay trên nó)… Ví dụ $i = 3$: sửa bit[3], bit[4], bit[8]. Mỗi bước bit 1 thấp nhất dịch sang trái, nên cũng chỉ $O(\log n)$ bước.
Tổng đoạn $[l, r]$ thì như mảng cộng dồn: query(r) - query(l - 1). Em bấm Tiếp để xem đường đi “nhảy lên” khi cập nhật và “nhảy xuống” khi hỏi tổng:
Xem code C++ / Python: cây Fenwick: cập nhật điểm, tổng đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long bit[200005]; // bit[i] = tổng a(i - lowbit(i), i]
void update(int i, long long x){ // a[i] += x
for(; i <= n; i += i & -i) bit[i] += x;
}
long long query(int i){ // a[1] + a[2] + ... + a[i]
long long s = 0;
for(; i > 0; i -= i & -i) s += bit[i];
return s;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i++){ long long x; cin >> x; update(i, x); }
while(q--){
int t; cin >> t;
if(t == 1){ int i; long long x; cin >> i >> x; update(i, x); }
else { int l, r; cin >> l >> r; cout << query(r) - query(l - 1) << "\n"; }
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
bit = [0] * (n + 1)
for i in range(1, n + 1): # dựng cây trong O(n)
bit[i] += int(data[1 + i])
j = i + (i & -i)
if j <= n:
bit[j] += bit[i]
def query(i): # a[1] + ... + a[i]
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
out, p = [], n + 2
for _ in range(q):
if data[p] == b'1': # a[i] += x
i, x = int(data[p + 1]), int(data[p + 2])
while i <= n:
bit[i] += x
i += i & -i
else:
l, r = int(data[p + 1]), int(data[p + 2])
out.append(query(r) - query(l - 1))
p += 3
print('\n'.join(map(str, out)))
main()void update(int i, long long x){ for(; i <= n; i += i & -i) bit[i] += x; }
long long query(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }update(0, x) lặp vô hạn vì 0 & -0 = 0. Luôn dùng chỉ số $1..n$.2. Bài “gán” $a_i = v$: Fenwick chỉ biết cộng. Phải giữ mảng
a riêng, rồi gọi update(i, v - a[i]); a[i] = v;.3. Tràn số: tổng có thể tới $2 \cdot 10^5 \cdot 10^9$, phải dùng
long long.Dựng cây nhanh hơn. Gọi $n$ lần update tốn $O(n \log n)$, thường là đủ. Bản Python ở trên dựng trong $O(n)$: duyệt $i$ tăng dần, cộng bit[i] (đã đủ) vào ô cha bit[i + lowbit(i)]. Fenwick chỉ làm tốt các phép có phép ngược như tổng (để có query(r) - query(l - 1)); với min/max trên đoạn bất kỳ, ta cần cây phân đoạn ở phần 4.
Phần 3Ứng dụng của Fenwick
Đếm nghịch thế bằng Fenwick
Ở bài 24 ta đếm cặp nghịch thế ($i < j$, $a_i > a_j$) bằng merge sort. Fenwick cho một cách nghĩ rất tự nhiên: duyệt từ trái sang phải, giữ một mảng đếm cnt[v] = số lần giá trị $v$ đã xuất hiện. Đến $a_j$, số phần tử đứng trước mà lớn hơn $a_j$ bằng (số phần tử đã gặp) − (số đã gặp mà $\le a_j$) = $j - \text{query}(a_j)$, rồi update(a_j, 1). Fenwick dựng trên trục giá trị chứ không phải trục vị trí!
Nén giá trị. Nếu $|a_i| \le 10^9$ thì không thể tạo mảng dài $10^9$. Nhưng ta chỉ quan tâm thứ tự lớn bé, nên thay mỗi số bằng thứ hạng của nó trong các giá trị khác nhau (sắp xếp, xoá trùng, tìm vị trí bằng lower_bound, như ở bài 16). Ví dụ $[100, -7, 100, 42] \to [3, 1, 3, 2]$.
| $j$ | $a_j$ | đã gặp | đã gặp mà $\le a_j$ | lớn hơn $a_j$ | tổng |
|---|---|---|---|---|---|
| 1 | 4 | {} | 0 | 0 | 0 |
| 2 | 2 | {4} | 0 | 1 | 1 |
| 3 | 5 | {2, 4} | 2 | 0 | 1 |
| 4 | 1 | {2, 4, 5} | 0 | 3 | 4 |
| 5 | 3 | {1, 2, 4, 5} | 2 | 2 | 6 |
Bảng 3. Đếm nghịch thế của dãy [4, 2, 5, 1, 3] bằng Fenwick trên trục giá trị. Cột “đã gặp mà ≤ $a_j$” chính là query($a_j$).
Xem code C++ / Python: đếm nghịch thế bằng Fenwick (có nén giá trị) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int bit[200005];
void update(int i){ for(; i <= m; i += i & -i) bit[i]++; }
int query(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<int> a(n), v;
for(auto &x : a) cin >> x;
v = a; // nén giá trị về 1..m
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
m = v.size();
long long res = 0;
for(int i = 0; i < n; i++){
int k = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
res += i - query(k); // số đã gặp mà lớn hơn a[i]
update(k); // đánh dấu đã gặp a[i]
}
cout << res;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
rank = {x: k + 1 for k, x in enumerate(sorted(set(a)))} # nén giá trị
m = len(rank)
bit = [0] * (m + 1)
res = 0
for i in range(n):
k = rank[a[i]]
s, j = 0, k # s = số đã gặp mà <= a[i]
while j > 0:
s += bit[j]; j -= j & -j
res += i - s
while k <= m: # đánh dấu đã gặp a[i]
bit[k] += 1; k += k & -k
print(res)
main()So với merge sort, cách này dễ mở rộng hơn: muốn đếm “số phần tử bên trái nhỏ hơn”, “số phần tử bên phải lớn hơn”, hay đếm bộ ba $i < j < k$ với $a_i < a_j < a_k$ (nhân hai đại lượng tại $j$) đều chỉ là đổi công thức query một chút.
Cộng đoạn, hỏi điểm bằng mảng hiệu
Bài toán ngược lại: thao tác 1 l r x cộng $x$ vào cả đoạn $a_l..a_r$, thao tác 2 i hỏi giá trị hiện tại của $a_i$. Nhớ lại mảng hiệu ở bài 13: cộng $x$ vào đoạn $[l, r]$ chỉ cần $D_l \mathrel{+}= x$, $D_{r+1} \mathrel{-}= x$, và giá trị thật là tổng tiền tố $D_1 + \cdots + D_i$. Hai việc này đúng là “cập nhật điểm” và “hỏi tổng tiền tố” của Fenwick! Vậy cộng đoạn là hai lần update, hỏi điểm là một lần query, tất cả $O(\log n)$.
Xem code C++ / Python: cộng đoạn, hỏi điểm bằng Fenwick trên mảng hiệu (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[200005], bit[200005]; // bit lưu mảng hiệu của các lần cộng
void update(int i, long long x){ for(; i <= n; i += i & -i) bit[i] += x; }
long long query(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--){
int t; cin >> t;
if(t == 1){
int l, r; long long x; cin >> l >> r >> x;
update(l, x); // từ l trở đi được cộng x
update(r + 1, -x); // từ r + 1 trở đi trừ lại
} else {
int i; cin >> i;
cout << a[i] + query(i) << "\n";
}
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + list(map(int, data[2:n + 2]))
bit = [0] * (n + 2) # mảng hiệu của các lần cộng
out, p = [], n + 2
for _ in range(q):
if data[p] == b'1':
l, r, x = int(data[p + 1]), int(data[p + 2]), int(data[p + 3])
p += 4
while l <= n: # cộng x từ l trở đi
bit[l] += x; l += l & -l
r += 1
while r <= n: # trừ x từ r + 1 trở đi
bit[r] -= x; r += r & -r
else:
i = int(data[p + 1]); p += 2
s, j = a[i], i
while j > 0:
s += bit[j]; j -= j & -j
out.append(s)
print('\n'.join(map(str, out)))
main()Cập nhật đoạn + hỏi điểm: Fenwick lưu mảng hiệu $D$.
Còn cập nhật đoạn + hỏi đoạn cũng làm được bằng hai Fenwick (bài tập 8), hoặc dùng cây phân đoạn với lazy propagation (phần 5).
Phần 4Cây phân đoạn (Segment Tree)
Cây phân đoạn là một cây nhị phân: gốc quản lý cả đoạn $[1, n]$; nút quản lý $[l, r]$ với $l < r$ có hai con quản lý $[l, m]$ và $[m + 1, r]$ với $m = \lfloor (l + r)/2 \rfloor$; lá quản lý đúng một phần tử. Mỗi nút lưu đáp án của đoạn mình (tổng, min, max…), tính từ hai con. Đây chính là cây đệ quy của merge sort ở bài 24, chỉ khác là ta giữ lại cả cây để dùng nhiều lần.
Cài bằng mảng. Đánh số gốc là 1, nút id có con trái 2·id, con phải 2·id + 1 (số đỏ trong hình). Cây có khoảng $\log_2 n$ tầng; khi $n$ không phải lũy thừa của 2, chỉ số lớn nhất có thể vượt $2n$ nhưng luôn nhỏ hơn $4n$, nên khai báo mảng $4n$ là an toàn.
Hình 2. Cây phân đoạn lưu tổng của dãy [5, 8, 6, 3, 2, 7, 2, 6]. Số đỏ là chỉ số nút trong mảng t: nút $i$ có hai con $2i$ và $2i + 1$.
Ba thao tác:
- build(id, l, r): lá thì
t[id] = a[l]; nút trong thì dựng hai con rồi gộp. Mỗi nút làm $O(1)$ việc, có $2n - 1$ nút nên tốn $O(n)$. - update(pos, v): đi từ gốc xuống lá chứa
pos(mỗi nút chọn con trái nếupos ≤ m), gán lá, rồi trên đường quay về tính lại từng nút cha. Đúng một đường gốc–lá: $O(\log n)$. - get(u, v): tại mỗi nút $[l, r]$ có ba trường hợp: nằm ngoài $[u, v]$ → trả về phần tử trung hoà (0 với tổng, $+\infty$ với min); nằm trọn trong $[u, v]$ → trả về luôn
t[id]; giao một phần → hỏi hai con rồi gộp.
Vì sao truy vấn chỉ $O(\log n)$? Có thể chứng minh ở mỗi tầng chỉ có tối đa 2 nút rơi vào trường hợp “giao một phần” (hai nút chứa hai đầu mút $u$ và $v$), các nút khác hoặc trọn hoặc ngoài và dừng ngay. Nên mỗi tầng thăm không quá 4 nút, tổng cộng khoảng $4 \log_2 n$ nút. Em thử đổi đoạn hỏi và phép gộp trong mô phỏng để tự đếm nhé:
Xem code C++ / Python: cây phân đoạn min: gán điểm, min đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q, a[200005], t[800005]; // cây cần 4n ô
void build(int id, int l, int r){
if(l == r){ t[id] = a[l]; return; }
int m = (l + r) / 2;
build(2 * id, l, m);
build(2 * id + 1, m + 1, r);
t[id] = min(t[2 * id], t[2 * id + 1]);
}
void update(int id, int l, int r, int pos, int v){ // gán a[pos] = v
if(l == r){ t[id] = v; return; }
int m = (l + r) / 2;
if(pos <= m) update(2 * id, l, m, pos, v);
else update(2 * id + 1, m + 1, r, pos, v);
t[id] = min(t[2 * id], t[2 * id + 1]);
}
int get(int id, int l, int r, int u, int v){ // min a[u..v]
if(v < l || r < u) return INT_MAX; // nằm ngoài
if(u <= l && r <= v) return t[id]; // nằm trọn
int m = (l + r) / 2; // giao một phần
return min(get(2 * id, l, m, u, v), get(2 * id + 1, m + 1, r, u, v));
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
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 << get(1, 1, n, x, y) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
INF = float('inf')
t = [INF] * n + [int(x) for x in data[2:n + 2]] # lá a[i] (i từ 0) ở ô n + i
for i in range(n - 1, 0, -1): # nút i có hai con 2i, 2i + 1
t[i] = min(t[2 * i], t[2 * i + 1])
out, p = [], n + 2
for _ in range(q):
typ, x, y = data[p], int(data[p + 1]), int(data[p + 2])
p += 3
if typ == b'1': # gán a[x] = y, đi từ lá lên gốc
i = x - 1 + n
t[i] = y
i >>= 1
while i:
t[i] = min(t[2 * i], t[2 * i + 1])
i >>= 1
else: # min trên [x, y], tức [l, r) với l = x - 1 + n, r = y + n
l, r, res = x - 1 + n, y + n, INF
while l < r:
if l & 1:
if t[l] < res: res = t[l]
l += 1
if r & 1:
r -= 1
if t[r] < res: res = t[r]
l >>= 1; r >>= 1
out.append(res)
print('\n'.join(map(str, out)))
main()i >>= 1); truy vấn nửa mở $[l, r)$ thì hai đầu cùng leo lên, đầu nào là “con lẻ ở bên trái” hoặc “con lẻ ở bên phải” thì lấy ô đó. Chỉ cần mảng $2n$ và chạy nhanh gấp mấy lần bản đệ quy.Khung chạy tay dưới đây đi qua đúng từng dòng của get. Em để ý mảng t: nút đang xét tô vàng, còn trên mảng a, đoạn của nút tô xanh lá nếu nằm trọn, đỏ nếu nằm ngoài:
Phần 5Lazy propagation và chọn cấu trúc nào
Giờ đề cho thao tác 1 l r x: cộng $x$ vào cả đoạn $[l, r]$, và 2 l r: hỏi tổng đoạn. Cập nhật từng lá thì mất $O(n)$ mỗi lần. Mẹo lazy propagation (cập nhật lười): khi cộng đoạn, gặp nút nằm trọn thì chỉ sửa tổng của nút đó ($t \mathrel{+}= x \cdot$ độ dài) và ghi vào nút một nhãn “hai con của ta còn nợ phép cộng $x$”, rồi dừng, không xuống dưới. Sau này, hễ có thao tác nào cần đi xuống các con của nút, ta đẩy nhãn (push) xuống hai con trước. Như vậy cả cộng đoạn lẫn hỏi đoạn đều đi theo đúng khuôn của truy vấn, chỉ $O(\log n)$.
Xem code C++ / Python: cây phân đoạn lazy: cộng đoạn, tổng đoạn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[200005], t[800005], lz[800005]; // lz[id]: phần cộng còn nợ hai con
void build(int id, int l, int r){
if(l == r){ t[id] = a[l]; return; }
int m = (l + r) / 2;
build(2 * id, l, m); build(2 * id + 1, m + 1, r);
t[id] = t[2 * id] + t[2 * id + 1];
}
void apply(int id, int l, int r, long long x){ // cộng x vào cả đoạn của nút id
t[id] += x * (r - l + 1);
lz[id] += x;
}
void push(int id, int l, int r){ // đẩy nhãn xuống hai con
if(lz[id] == 0) return;
int m = (l + r) / 2;
apply(2 * id, l, m, lz[id]);
apply(2 * id + 1, m + 1, r, lz[id]);
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, long long x){
if(v < l || r < u) return;
if(u <= l && r <= v){ apply(id, l, r, x); return; } // nằm trọn: dán nhãn rồi dừng
push(id, l, r);
int m = (l + r) / 2;
update(2 * id, l, m, u, v, x);
update(2 * id + 1, m + 1, r, u, v, x);
t[id] = t[2 * id] + t[2 * id + 1];
}
long long get(int id, int l, int r, int u, int v){
if(v < l || r < u) return 0;
if(u <= l && r <= v) return t[id];
push(id, l, r);
int m = (l + r) / 2;
return get(2 * id, l, m, u, v) + get(2 * id + 1, m + 1, r, u, v);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
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){ long long x; cin >> x; update(1, 1, n, l, r, x); }
else cout << get(1, 1, n, l, r) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
t = [0] * (4 * n)
lz = [0] * (4 * n) # phần cộng còn nợ hai con
def build(i, l, r):
if l == r:
t[i] = a[l]; return
m = (l + r) // 2
build(2 * i, l, m); build(2 * i + 1, m + 1, r)
t[i] = t[2 * i] + t[2 * i + 1]
def push(i, l, r): # đẩy nhãn xuống hai con
x = lz[i]
if x:
m = (l + r) // 2
t[2 * i] += x * (m - l + 1); lz[2 * i] += x
t[2 * i + 1] += x * (r - m); lz[2 * i + 1] += x
lz[i] = 0
def update(i, l, r, u, v, x):
if v < l or r < u:
return
if u <= l and r <= v: # nằm trọn: dán nhãn rồi dừng
t[i] += x * (r - l + 1); lz[i] += x
return
push(i, l, r)
m = (l + r) // 2
update(2 * i, l, m, u, v, x); update(2 * i + 1, m + 1, r, u, v, x)
t[i] = t[2 * i] + t[2 * i + 1]
def get(i, l, r, u, v):
if v < l or r < u:
return 0
if u <= l and r <= v:
return t[i]
push(i, l, r)
m = (l + r) // 2
return get(2 * i, l, m, u, v) + get(2 * i + 1, m + 1, r, u, v)
build(1, 1, n)
out, p = [], n + 2
for _ in range(q):
if data[p] == b'1':
update(1, 1, n, int(data[p + 1]), int(data[p + 2]), int(data[p + 3])); p += 4
else:
out.append(get(1, 1, n, int(data[p + 1]), int(data[p + 2]))); p += 3
print('\n'.join(map(str, out)))
main()push trước khi đi xuống con, trong cả update lẫn get.2. Sau khi cập nhật hai con, phải tính lại
t[id] từ hai con. Và nhãn là cộng dồn (lz += x), không phải gán. Bản Python đệ quy ở trên dễ đọc nhưng chậm; với $n, q = 2 \cdot 10^5$ nên dùng hai Fenwick như bài tập 8.| Cấu trúc | Dựng | Cập nhật | Truy vấn | Làm được | Dùng khi |
|---|---|---|---|---|---|
| Mảng cộng dồn | $O(n)$ | $O(n)$ | $O(1)$ | tổng, đếm | không có cập nhật |
| Sparse table | $O(n \log n)$ | không | $O(1)$ | min, max, gcd | min/max đoạn, dãy cố định |
| Fenwick | $O(n)$ | $O(\log n)$ | $O(\log n)$ | tổng, đếm, (min tiền tố) | tổng/đếm có cập nhật, code ngắn |
| Cây phân đoạn | $O(n)$ | $O(\log n)$ | $O(\log n)$ | mọi phép kết hợp | min/max/gcd có cập nhật |
| Cây phân đoạn + lazy | $O(n)$ | $O(\log n)$ cả đoạn | $O(\log n)$ | cộng/gán đoạn + tổng/min đoạn | cập nhật cả đoạn |
Bảng 4. So sánh các cấu trúc trả lời truy vấn đoạn. Sparse table lưu min của mọi đoạn dài $2^k$, hỏi min đoạn bằng hai đoạn chồng nhau, nhưng không cho sửa.
Khi đi thi: bài chỉ cần tổng/đếm thì viết Fenwick (5 dòng, khó sai). Cần min/max/gcd có sửa, hoặc thông tin phức tạp hơn, thì viết cây phân đoạn. Chỉ khi có cập nhật cả đoạn mới cần lazy. Và nhớ luôn tự hỏi: có thật cần cập nhật không? Nếu không, mảng cộng dồn là đủ.
- Dãy nghịch thế (NKINV) (Khá)
- Collecting Numbers II (CSES 2217) (Khá)
- Đếm Đoạn Bao Chứa (Khá)
- SEQ (Khá)
- Chênh Lệch Lớn Nhất (Khó)
- Ăn Buffet (Khó)
Bài tậpLuyện Fenwick và cây phân đoạn
Lớp có $n$ tổ, tổ $i$ có điểm thi đua $a_i$ ($n, q \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Có $q$ thao tác: 1 i v: điểm của tổ $i$ được sửa thành $v$ ($|v| \le 10^9$); 2 l r: in tổng điểm các tổ từ $l$ đến $r$.
4 4
3 1 4 1
2 1 4
1 2 10
2 2 3
2 1 19
14
3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[200005], bit[200005];
void update(int i, long long x){ for(; i <= n; i += i & -i) bit[i] += x; }
long long query(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i++){ cin >> a[i]; update(i, a[i]); }
while(q--){
int t; long long x, y; cin >> t >> x >> y;
if(t == 1){ update(x, y - a[x]); a[x] = y; } // gán = cộng phần chênh lệch
else cout << query(y) - query(x - 1) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
bit = a[:] # dựng Fenwick trong O(n)
for i in range(1, n + 1):
j = i + (i & -i)
if j <= n:
bit[j] += bit[i]
out, p = [], n + 2
for _ in range(q):
t, x, y = data[p], int(data[p + 1]), int(data[p + 2])
p += 3
if t == b'1':
d, a[x] = y - a[x], y # gán = cộng phần chênh lệch
while x <= n:
bit[x] += d; x += x & -x
else:
s, i = 0, y
while i > 0:
s += bit[i]; i -= i & -i
i = x - 1
while i > 0:
s -= bit[i]; i -= i & -i
out.append(s)
print('\n'.join(map(str, out)))
main()Trạm khí tượng ghi nhiệt độ $n$ ngày $a_1..a_n$ ($n, q \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Có $q$ thao tác: 1 i v: sửa nhiệt độ ngày $i$ thành $v$; 2 l r: in nhiệt độ thấp nhất trong các ngày $l..r$ và ngày sớm nhất đạt nhiệt độ đó.
6 3
4 2 7 2 9 1
2 1 5
1 2 5
2 1 52 2
2 4📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
min của pair trong C++. Phần tử trung hoà là $(+\infty, +\infty)$. Ví dụ: đoạn 1..5 có hai ngày lạnh 2 độ (ngày 2 và 4), chọn ngày 2; sau khi sửa ngày 2 thành 5 thì còn ngày 4. Bản Python ghép cặp thành một số $v \cdot 2^{18} + i$ để so sánh nhanh.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, int> P; // (nhiệt độ, ngày)
int n, q;
long long a[200005];
P t[800005];
const P NONE = {LLONG_MAX, INT_MAX};
void build(int id, int l, int r){
if(l == r){ t[id] = {a[l], l}; return; }
int m = (l + r) / 2;
build(2 * id, l, m); build(2 * id + 1, m + 1, r);
t[id] = min(t[2 * id], t[2 * id + 1]);
}
void update(int id, int l, int r, int pos, long long v){
if(l == r){ t[id] = {v, l}; return; }
int m = (l + r) / 2;
if(pos <= m) update(2 * id, l, m, pos, v); else update(2 * id + 1, m + 1, r, pos, v);
t[id] = min(t[2 * id], t[2 * id + 1]);
}
P get(int id, int l, int r, int u, int v){
if(v < l || r < u) return NONE;
if(u <= l && r <= v) return t[id];
int m = (l + r) / 2;
return min(get(2 * id, l, m, u, v), get(2 * id + 1, m + 1, r, u, v));
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
while(q--){
int type; long long x, y; cin >> type >> x >> y;
if(type == 1) update(1, 1, n, x, y);
else { P r = get(1, 1, n, x, y); cout << r.first << " " << r.second << "\n"; }
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
SH, MASK = 18, (1 << 18) - 1 # cặp (v, i) -> v * 2^18 + i, so sánh như so cặp
INF = float('inf')
t = [INF] * n + [int(data[2 + i]) * (1 << SH) + (i + 1) for i in range(n)]
for i in range(n - 1, 0, -1):
t[i] = min(t[2 * i], t[2 * i + 1])
out, p = [], n + 2
for _ in range(q):
typ, x, y = data[p], int(data[p + 1]), int(data[p + 2])
p += 3
if typ == b'1':
i = x - 1 + n
t[i] = y * (1 << SH) + x
i >>= 1
while i:
t[i] = min(t[2 * i], t[2 * i + 1]); i >>= 1
else:
l, r, res = x - 1 + n, y + n, INF
while l < r:
if l & 1:
if t[l] < res: res = t[l]
l += 1
if r & 1:
r -= 1
if t[r] < res: res = t[r]
l >>= 1; r >>= 1
out.append('%d %d' % (res >> SH, res & MASK))
print('\n'.join(out))
main()Cho dãy $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Đếm số cặp $(i, j)$ với $i < j$ và $a_i > a_j$. Hãy giải bằng cây Fenwick.
5
4 2 5 1 36📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
update(a_j). Sáu cặp: (4,2), (4,1), (4,3), (2,1), (5,1), (5,3). Đáp án có thể tới $2 \cdot 10^{10}$, nhớ long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m;
int bit[200005];
void update(int i){ for(; i <= m; i += i & -i) bit[i]++; }
int query(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<int> a(n), v;
for(auto &x : a) cin >> x;
v = a; // nén giá trị về 1..m
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
m = v.size();
long long res = 0;
for(int i = 0; i < n; i++){
int k = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
res += i - query(k); // số đã gặp mà lớn hơn a[i]
update(k); // đánh dấu đã gặp a[i]
}
cout << res;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
rank = {x: k + 1 for k, x in enumerate(sorted(set(a)))} # nén giá trị
m = len(rank)
bit = [0] * (m + 1)
res = 0
for i in range(n):
k = rank[a[i]]
s, j = 0, k # s = số đã gặp mà <= a[i]
while j > 0:
s += bit[j]; j -= j & -j
res += i - s
while k <= m: # đánh dấu đã gặp a[i]
bit[k] += 1; k += k & -k
print(res)
main()$n$ bạn lần lượt bước vào hàng, bạn thứ $i$ cao $h_i$ ($n \le 2 \cdot 10^5$, $1 \le h_i \le 10^9$). Khi bạn $i$ vào, bạn ấy đếm xem trong $i - 1$ bạn đã đứng trước có bao nhiêu bạn thấp hơn hẳn mình. In ra $n$ số đếm được.
6
5 3 8 3 6 10 0 2 0 3 0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
query(rank - 1); rồi update(rank, 1). Ví dụ bạn cao 6 thấy 5, 3, 3 thấp hơn (8 thì không) → 3.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m, bit[200005];
void update(int i){ for(; i <= m; i += i & -i) bit[i]++; }
int query(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
vector<int> h(n), v;
for(auto &x : h) cin >> x;
v = h;
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
m = v.size();
for(int i = 0; i < n; i++){
int k = lower_bound(v.begin(), v.end(), h[i]) - v.begin() + 1;
cout << query(k - 1) << " "; // số đã gặp có hạng < k
update(k);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
h = list(map(int, data[1:n + 1]))
rank = {x: k + 1 for k, x in enumerate(sorted(set(h)))}
m = len(rank)
bit = [0] * (m + 1)
out = []
for x in h:
k = rank[x]
s, j = 0, k - 1 # số đã gặp có hạng < k
while j > 0:
s += bit[j]; j -= j & -j
out.append(s)
while k <= m:
bit[k] += 1; k += k & -k
print(*out)
main()Vườn có $n$ luống rau, luống $i$ cao $a_i$ ($n, q \le 2 \cdot 10^5$, $0 \le a_i \le 10^9$). Có $q$ thao tác: 1 l r x: các luống $l..r$ đều cao thêm $x$ ($|x| \le 10^9$); 2 i: in độ cao hiện tại của luống $i$.
5 5
1 2 3 4 5
1 2 4 10
2 3
2 5
1 1 5 -1
2 213
5
11📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
update(l, x) và update(r + 1, -x); độ cao luống $i$ là $a_i$ + query(i). Ví dụ luống 3: $3 + 10 = 13$; luống 2 sau hai lần tưới: $2 + 10 - 1 = 11$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[200005], bit[200005]; // bit lưu mảng hiệu của các lần cộng
void update(int i, long long x){ for(; i <= n; i += i & -i) bit[i] += x; }
long long query(int i){ long long s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
while(q--){
int t; cin >> t;
if(t == 1){
int l, r; long long x; cin >> l >> r >> x;
update(l, x); // từ l trở đi được cộng x
update(r + 1, -x); // từ r + 1 trở đi trừ lại
} else {
int i; cin >> i;
cout << a[i] + query(i) << "\n";
}
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + list(map(int, data[2:n + 2]))
bit = [0] * (n + 2) # mảng hiệu của các lần cộng
out, p = [], n + 2
for _ in range(q):
if data[p] == b'1':
l, r, x = int(data[p + 1]), int(data[p + 2]), int(data[p + 3])
p += 4
while l <= n: # cộng x từ l trở đi
bit[l] += x; l += l & -l
r += 1
while r <= n: # trừ x từ r + 1 trở đi
bit[r] -= x; r += r & -r
else:
i = int(data[p + 1]); p += 2
s, j = a[i], i
while j > 0:
s += bit[j]; j -= j & -j
out.append(s)
print('\n'.join(map(str, out)))
main()Một chiếc hộp ban đầu rỗng. Có $q$ thao tác ($q \le 2 \cdot 10^5$, $1 \le x \le 10^6$): 1 x: bỏ số $x$ vào hộp; 2 x: lấy một số $x$ ra khỏi hộp (nếu hộp không có $x$ thì bỏ qua); 3 k: in số nhỏ thứ $k$ trong hộp (tính cả số trùng), in -1 nếu hộp có ít hơn $k$ số.
7
1 5
1 2
1 5
3 2
2 5
3 2
3 35
5
-1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
bit đếm số lần xuất hiện. Số nhỏ thứ $k$ là $x$ nhỏ nhất có query(x) ≥ k. Thay vì tìm kiếm nhị phân bên ngoài ($O(\log^2)$), ta đi xuống trên cây Fenwick: thử các bước nhảy $2^{19}, 2^{18}, \ldots, 1$; nếu bit[pos + step] < k thì nhảy tới và trừ $k$ đi bit[pos + step] (vì ô đó đúng là tổng đoạn $(pos, pos + step]$). Cuối cùng đáp án là pos + 1, chỉ $O(\log V)$. Ví dụ: hộp {2, 5, 5} có số nhỏ thứ 2 là 5; lấy ra một số 5 còn {2, 5}, chỉ có 2 số nên hỏi thứ 3 in −1.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int V = 1000000, LOG = 20; // 2^20 > V
int bit[V + 1], cnt[V + 1], total = 0;
void update(int i, int x){ for(; i <= V; i += i & -i) bit[i] += x; }
int kth(int k){ // số nhỏ nhất có tổng tiền tố >= k
int pos = 0;
for(int s = 1 << (LOG - 1); s > 0; s >>= 1)
if(pos + s <= V && bit[pos + s] < k){
pos += s;
k -= bit[pos];
}
return pos + 1;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int q; cin >> q;
while(q--){
int t, x; cin >> t >> x;
if(t == 1){ cnt[x]++; total++; update(x, 1); }
else if(t == 2){ if(cnt[x] > 0){ cnt[x]--; total--; update(x, -1); } }
else cout << (x > total ? -1 : kth(x)) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
q = int(data[0])
V = 10 ** 6
bit = [0] * (V + 1)
cnt = [0] * (V + 1)
total = 0
out = []
for k in range(q):
t, x = data[1 + 2 * k], int(data[2 + 2 * k])
if t == b'1' or (t == b'2' and cnt[x] > 0):
d = 1 if t == b'1' else -1
cnt[x] += d; total += d
while x <= V:
bit[x] += d; x += x & -x
elif t == b'3':
if x > total:
out.append(-1); continue
pos, s = 0, 1 << 19 # đi xuống trên cây Fenwick
while s:
if pos + s <= V and bit[pos + s] < x:
pos += s
x -= bit[pos]
s >>= 1
out.append(pos + 1)
print('\n'.join(map(str, out)))
main()Cho dãy $n$ số nguyên ($n, q \le 10^5$, $|a_i| \le 10^9$) và $q$ câu hỏi, mỗi câu gồm $l, r, x$ ($|x| \le 10^9$): có bao nhiêu chỉ số $i \in [l, r]$ mà $a_i > x$? Dãy không thay đổi. In đáp án theo đúng thứ tự câu hỏi.
5 3
3 7 1 9 4
1 5 3
2 4 8
3 3 03
1
1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
query(r) - query(l - 1). Mỗi phần tử chỉ được đưa vào một lần nên tổng $O((n + q) \log n)$. Nhớ lưu chỉ số gốc của câu hỏi để in đúng thứ tự. Ví dụ câu 1: trong cả dãy có 7, 9, 4 lớn hơn 3.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q, bit[100005];
void update(int i){ for(; i <= n; i += i & -i) bit[i]++; }
int query(int i){ int s = 0; for(; i > 0; i -= i & -i) s += bit[i]; return s; }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
vector<pair<int, int>> e(n); // (giá trị, vị trí)
for(int i = 0; i < n; i++){ cin >> e[i].first; e[i].second = i + 1; }
sort(e.rbegin(), e.rend()); // giá trị giảm dần
vector<array<int, 4>> qs(q); // (x, l, r, chỉ số câu hỏi)
for(int k = 0; k < q; k++){ cin >> qs[k][1] >> qs[k][2] >> qs[k][0]; qs[k][3] = k; }
sort(qs.rbegin(), qs.rend()); // x giảm dần
vector<int> ans(q);
int p = 0;
for(auto &c : qs){
while(p < n && e[p].first > c[0]) update(e[p++].second); // thêm mọi số > x
ans[c[3]] = query(c[2]) - query(c[1] - 1);
}
for(int k = 0; k < q; k++) cout << ans[k] << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = list(map(int, data[2:n + 2]))
order = sorted(range(n), key=lambda i: -a[i]) # vị trí, giá trị giảm dần
qs = []
for k in range(q):
l, r, x = int(data[n + 2 + 3 * k]), int(data[n + 3 + 3 * k]), int(data[n + 4 + 3 * k])
qs.append((x, l, r, k))
qs.sort(reverse=True) # x giảm dần
bit = [0] * (n + 1)
ans = [0] * q
p = 0
for x, l, r, k in qs:
while p < n and a[order[p]] > x: # thêm mọi số > x
i = order[p] + 1
while i <= n:
bit[i] += 1; i += i & -i
p += 1
s, i = 0, r
while i > 0:
s += bit[i]; i -= i & -i
i = l - 1
while i > 0:
s -= bit[i]; i -= i & -i
ans[k] = s
print('\n'.join(map(str, ans)))
main()Cho dãy $n$ số nguyên ($n, q \le 2 \cdot 10^5$, $|a_i| \le 10^9$). Có $q$ thao tác: 1 l r x: cộng $x$ ($|x| \le 10^6$) vào mọi $a_l..a_r$; 2 l r: in tổng $a_l + \cdots + a_r$.
8 3
3 1 4 1 5 9 2 6
1 2 7 2
2 4 5
2 1 810
43📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
B1 cho $D_j$ và B2 cho $j \cdot D_j$; cộng đoạn là 4 lần update, tổng tiền tố là $(p + 1) \cdot B1(p) - B2(p)$ cộng tiền tố ban đầu. Ví dụ: sau khi cộng 2 vào đoạn 2..7 thì $a_4 + a_5 = 3 + 7 = 10$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[200005], t[800005], lz[800005]; // lz[id]: phần cộng còn nợ hai con
void build(int id, int l, int r){
if(l == r){ t[id] = a[l]; return; }
int m = (l + r) / 2;
build(2 * id, l, m); build(2 * id + 1, m + 1, r);
t[id] = t[2 * id] + t[2 * id + 1];
}
void apply(int id, int l, int r, long long x){ // cộng x vào cả đoạn của nút id
t[id] += x * (r - l + 1);
lz[id] += x;
}
void push(int id, int l, int r){ // đẩy nhãn xuống hai con
if(lz[id] == 0) return;
int m = (l + r) / 2;
apply(2 * id, l, m, lz[id]);
apply(2 * id + 1, m + 1, r, lz[id]);
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, long long x){
if(v < l || r < u) return;
if(u <= l && r <= v){ apply(id, l, r, x); return; } // nằm trọn: dán nhãn rồi dừng
push(id, l, r);
int m = (l + r) / 2;
update(2 * id, l, m, u, v, x);
update(2 * id + 1, m + 1, r, u, v, x);
t[id] = t[2 * id] + t[2 * id + 1];
}
long long get(int id, int l, int r, int u, int v){
if(v < l || r < u) return 0;
if(u <= l && r <= v) return t[id];
push(id, l, r);
int m = (l + r) / 2;
return get(2 * id, l, m, u, v) + get(2 * id + 1, m + 1, r, u, v);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
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){ long long x; cin >> x; update(1, 1, n, l, r, x); }
else cout << get(1, 1, n, l, r) << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
P = [0] * (n + 1) # tổng tiền tố ban đầu
for i in range(1, n + 1):
P[i] = P[i - 1] + int(data[1 + i])
B1 = [0] * (n + 2) # Fenwick của D[j]
B2 = [0] * (n + 2) # Fenwick của j * D[j]
def add(i, x):
y = x * i
while i <= n:
B1[i] += x; B2[i] += y; i += i & -i
def pre(p): # tổng a[1..p] hiện tại
s1 = s2 = 0
i = p
while i > 0:
s1 += B1[i]; s2 += B2[i]; i -= i & -i
return P[p] + (p + 1) * s1 - s2
out, p = [], n + 2
for _ in range(q):
if data[p] == b'1':
l, r, x = int(data[p + 1]), int(data[p + 2]), int(data[p + 3]); p += 4
add(l, x)
if r + 1 <= n:
add(r + 1, -x)
else:
l, r = int(data[p + 1]), int(data[p + 2]); p += 3
out.append(pre(r) - pre(l - 1))
print('\n'.join(map(str, out)))
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét