Cây Fenwick (BIT)

Mức độ: Nâng cao

Tổng tiền tố trả lời tổng đoạn bằng một phép trừ, nhưng khi dãy thay đổi (sửa một phần tử) thì phải tính lại cả mảng tiền tố, mất n bước. Đề có 10⁵ lần sửa xen kẽ 10⁵ câu hỏi thì cách nào cũng tới 10¹⁰ bước. Cây Fenwick (còn gọi là BIT, Binary Indexed Tree) làm cả hai việc trong khoảng log₂n bước.

Ý tưởng: mỗi ô giữ tổng của một khúc

Đánh số từ 1. Ô bit[i] giữ tổng của khúc kết thúc tại i, có độ dài bằng bit 1 thấp nhất của i (viết i dưới dạng nhị phân, lấy lũy thừa của 2 ứng với chữ số 1 cuối cùng). Bit thấp nhất tính bằng i & -i.

i	nhị phân	i & -i	bit[i] giữ tổng
1	0001	1	a1
2	0010	2	a1 + a2
3	0011	1	a3
4	0100	4	a1 + … + a4
5	0101	1	a5
6	0110	2	a5 + a6
7	0111	1	a7
8	1000	8	a1 + … + a8

Tổng tiền tố đến i: cộng bit[i], rồi nhảy về trước khúc vừa cộng (i -= i & -i), lặp đến khi i = 0. Ví dụ tổng đến 7: bit[7] (a₇) + bit[6] (a₅ + a₆) + bit[4] (a₁ đến a₄). Mỗi lần nhảy xóa một bit 1 của i, nên không quá log₂n lần.

Cộng v vào a_i: mọi ô có khúc chứa vị trí i đều phải cộng v. Đó là i, rồi i += i & -i, lặp đến khi vượt n. Ví dụ cộng vào a₃: sửa bit[3], bit[4], bit[8]. Mỗi lần nhảy, bit thấp nhất dịch lên ít nhất một bậc, nên cũng không quá log₂n lần.

Python

import sys

def cong(i, v):                  # a[i] += v
    while i <= n:
        bit[i] += v
        i += i & -i

def tong_tien_to(i):             # a[1] + ... + a[i]
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
bit = [0] * (n + 1)
for i in range(1, n + 1):
    cong(i, int(du_lieu[1 + i]))
ket_qua = []
vi_tri = 2 + n
for _ in range(q):
    loai, x, y = du_lieu[vi_tri], int(du_lieu[vi_tri + 1]), int(du_lieu[vi_tri + 2])
    vi_tri += 3
    if loai == '1':
        cong(x, y)                                        # cộng y vào a[x]
    else:
        ket_qua.append(tong_tien_to(y) - tong_tien_to(x - 1))   # tổng từ x đến y
print("\n".join(map(str, ket_qua)))

C++

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<long long> bit;

void cong(int i, long long v) {       // a[i] += v
    for (; i <= n; i += i & -i) bit[i] += v;
}

long long tongTienTo(int i) {         // a[1] + ... + 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);
    int q;
    cin >> n >> q;
    bit.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        cong(i, x);
    }
    while (q--) {
        int loai, x;
        long long y;
        cin >> loai >> x >> y;
        if (loai == 1) cong(x, y);                                   // cộng y vào a[x]
        else cout << tongTienTo(y) - tongTienTo(x - 1) << "\n";      // tổng từ x đến y
    }
    return 0;
}

Các cách dùng hay gặp

Bài toán	Cách dùng Fenwick
sửa một phần tử, hỏi tổng đoạn	như chương trình trên
cộng v vào cả đoạn [l, r], hỏi một phần tử	Fenwick trên mảng hiệu: cộng v tại l, trừ v tại r + 1; giá trị ai là tổng tiền tố đến i
đếm số phần tử nhỏ hơn x đã gặp	Fenwick trên giá trị: gặp x thì cộng 1 vào ô x; số phần tử nhỏ hơn x là tổng tiền tố đến x - 1
giá trị lớn tới 109	rời rạc hóa trước

Đếm nghịch thế

Nghịch thế là cặp i đứng trước j mà a_i lớn hơn a_j. Đi từ trái sang phải, trước khi thêm a_j vào Fenwick (theo giá trị), đếm số phần tử đã thêm lớn hơn a_j: bằng (số đã thêm) - (tổng tiền tố đến a_j).

Dãy 3 1 4 2:

aj	đã thêm	lớn hơn aj	nghịch thế cộng dồn
3		0	0
1	3	1	1
4	3 1	0	1
2	3 1 4	2 (là 3 và 4)	3

Cả bài khoảng n × log₂n bước, so với n² / 2 cặp nếu thử hết.

Luyện tập

Gồm 20 bài, chia thành 5 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Sửa phần tử, hỏi tổng

Bài 1. Cộng một phần tử, tổng đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng là 1 i v (cộng v vào a_i, |v| ≤ 10⁹) hoặc 2 l r (hỏi tổng a_l + … + a_r). In ra đáp số các câu hỏi loại 2.

Ví dụ:

Nhập	In ra
5 5 1 2 3 4 5 2 1 3 1 2 10 2 1 3 2 3 5 1 5 -5	6 16 12

Kiểm tra: nhập

8 6
4 -2 7 0 3 3 -8 1
2 2 6
1 4 5
2 1 8
1 1 -4
2 1 4
2 8 8

Xem đáp số

11
13
10
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Sửa giá trị, tổng đoạn

Giống bài 1, nhưng thao tác loại 1 là 1 i v: gán a_i = v (thay vì cộng). Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), dòng thứ hai có n số, q dòng sau là các thao tác. In ra đáp số các câu hỏi loại 2.

Ví dụ:

Nhập	In ra
5 4 1 2 3 4 5 1 3 10 2 1 5 1 3 0 2 2 4	22 6

Kiểm tra: nhập

6 6
5 5 5 5 5 5
2 1 6
1 6 -5
1 1 -5
2 1 6
1 6 20
2 4 6

Xem đáp số

30
10
30

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Cộng đoạn, hỏi một phần tử

Dãy n số ban đầu toàn 0. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), q dòng sau mỗi dòng là 1 l r v (cộng v vào mọi a_l, …, a_r, |v| ≤ 10⁹) hoặc 2 i (hỏi a_i). In ra đáp số các câu hỏi loại 2.

Ví dụ:

Nhập	In ra
5 5 1 2 4 3 2 3 1 1 2 -1 2 2 2 5	3 2 0

Kiểm tra: nhập

8 7
1 1 8 2
1 3 5 4
2 4
1 4 4 -10
2 4
2 6
2 1

Xem đáp số

6
-4
2
2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Cộng đoạn, tổng đoạn

Dãy n số ban đầu toàn 0. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), q dòng sau mỗi dòng là 1 l r v (cộng v vào mọi a_l, …, a_r, |v| ≤ 10⁶) hoặc 2 l r (hỏi tổng a_l + … + a_r). In ra đáp số các câu hỏi loại 2.

Ví dụ:

Nhập	In ra
5 4 1 1 3 2 2 2 5 1 2 5 1 2 1 5	4 10

Kiểm tra: nhập

8 6
1 1 8 1
1 4 6 3
2 1 3
2 4 8
1 2 2 -7
2 1 8

Xem đáp số

3
14
10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Công tắc đèn

Có n bóng đèn, ban đầu đều tắt. Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), q dòng sau mỗi dòng là 1 l r (bấm công tắc mọi bóng từ l đến r: bóng đang tắt thì bật, đang bật thì tắt) hoặc 2 i (hỏi bóng i đang bật hay tắt). Với câu hỏi loại 2, in ra 1 nếu bật, 0 nếu tắt.

Ví dụ:

Nhập	In ra
5 5 1 1 3 2 2 1 2 5 2 2 2 5	1 0 1

Kiểm tra: nhập

8 7
1 1 8
1 3 6
2 4
1 4 4
2 4
2 8
2 2

Xem đáp số

0
1
1
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Đếm bằng Fenwick trên giá trị

Bài 6. Đếm nghịch thế

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số cặp vị trí i đứng trước j mà a_i lớn hơn a_j.

Ví dụ:

Nhập	In ra
4 3 1 4 2	3

Kiểm tra: nhập

10
1000000000 -5 7 7 -1000000000 0 3 3 12 -5

Xem đáp số

24

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Số nhỏ hơn ở bên phải

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Với mỗi vị trí i, in ra số phần tử đứng sau i và nhỏ hơn a_i.

Ví dụ:

Nhập	In ra
5 5 2 6 1 3	3 1 2 0 0

Kiểm tra: nhập

10
4 -1 4 9 0 2 -7 9 3 1

Xem đáp số

6 1 5 5 1 2 0 2 1 0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Bộ ba tăng dần

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số bộ ba vị trí i đứng trước j, j đứng trước k mà a_i nhỏ hơn a_j và a_j nhỏ hơn a_k.

Ví dụ:

Nhập	In ra
5 1 3 2 4 5	7

Kiểm tra: nhập

10
5 1 7 3 3 8 2 9 6 10

Xem đáp số

39

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Thứ hạng ngay khi thi xong

n bạn lần lượt thi, bạn thứ i được điểm s_i. Ngay khi bạn i thi xong, xếp hạng bạn i trong số i bạn đã thi: hạng bằng 1 cộng số bạn đã thi có điểm cao hơn. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số s_i (0 ≤ s_i ≤ 10⁹). In ra hạng của từng bạn ngay khi thi xong.

Ví dụ:

Nhập	In ra
5 70 90 80 90 60	1 1 2 1 5

Kiểm tra: nhập

10
500 300 500 800 100 800 700 0 900 500

Xem đáp số

1 2 1 1 5 1 3 8 1 5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Đoạn có trung bình ít nhất k

Dòng đầu có n, k (1 ≤ n ≤ 2 × 10⁵, |k| ≤ 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số đoạn liên tiếp có trung bình cộng ít nhất k.

Ví dụ:

Nhập	In ra
4 3 1 5 2 4	7

Kiểm tra: nhập

10 0
3 -4 2 -1 0 5 -6 1 1 -2

Xem đáp số

29

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Đổi chỗ kề nhau để biến xâu

Nhập hai xâu s và t cùng độ dài (1 ≤ độ dài ≤ 2 × 10⁵), gồm chữ cái thường, t là một cách sắp xếp lại các chữ cái của s. Mỗi bước được đổi chỗ hai ký tự kề nhau của s. In ra số bước ít nhất để biến s thành t.

Ví dụ:

Nhập	In ra
abc cab	2

Kiểm tra: nhập

bumbii
imbuib

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Tìm phần tử thứ k

Bài 12. Túi số, lấy số nhỏ thứ k

Một túi ban đầu rỗng. Dòng đầu có q (1 ≤ q ≤ 2 × 10⁵), q dòng sau mỗi dòng là 1 x (bỏ số x vào túi, 1 ≤ x ≤ 10⁶), 2 x (lấy một số x ra khỏi túi, chắc chắn túi đang có x) hoặc 3 k (hỏi số nhỏ thứ k trong túi, chắc chắn túi có ít nhất k số). In ra đáp số các câu hỏi loại 3.

Ví dụ:

Nhập	In ra
7 1 5 1 2 1 8 3 2 2 5 1 2 3 2	5 2

Kiểm tra: nhập

9
1 100
1 100
1 7
3 3
2 100
3 2
1 1000000
1 1
3 4

Xem đáp số

100
100
1000000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đếm để loại

n bạn đánh số 1 đến n đứng thành vòng tròn. Bắt đầu từ bạn 1, đếm 1, 2, …, k theo vòng; bạn được đếm số k bị loại, rồi đếm lại từ 1 bắt đầu từ bạn kế tiếp. Lặp đến khi hết người. Dòng duy nhất có n, k (1 ≤ n ≤ 2 × 10⁵, 1 ≤ k ≤ 10⁹). In ra thứ tự các bạn bị loại.

Ví dụ: nhập 7 3 thì in ra 3 6 2 7 5 1 4.

Kiểm tra: nhập 10 4.

Xem đáp số

4 8 2 7 3 10 9 1 6 5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Xử lý offline

Bài 14. Số giá trị khác nhau trong đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁹), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra số giá trị khác nhau trong đoạn a_l, …, a_r.

Ví dụ:

Nhập	In ra
6 3 1 2 1 3 2 2 1 3 2 6 4 4	2 3 1

Kiểm tra: nhập

10 4
5 5 7 5 9 7 7 1 9 5
1 10
2 4
3 7
8 10

Xem đáp số

4
2
3
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Tổng các số không vượt quá x trong đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (1 ≤ a_i ≤ 10⁹), q dòng sau mỗi dòng có l, r, x. Với mỗi câu hỏi, in ra tổng các a_i với l ≤ i ≤ r và a_i ≤ x.

Ví dụ:

Nhập	In ra
5 3 4 9 2 7 5 1 5 5 2 4 8 3 3 1	11 9 0

Kiểm tra: nhập

8 4
10 3 8 3 15 1 6 12
1 8 6
2 5 3
4 8 12
1 1 9

Xem đáp số

13
6
22
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Đếm điểm trong hình chữ nhật

Có n điểm trên mặt phẳng và q hình chữ nhật có cạnh song song với trục. Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), n dòng sau mỗi dòng có x, y của một điểm, q dòng sau mỗi dòng có x₁, y₁, x₂, y₂ (x₁ ≤ x₂, y₁ ≤ y₂); mọi tọa độ là số nguyên có giá trị tuyệt đối không quá 10⁹. Với mỗi hình chữ nhật, in ra số điểm nằm trong hoặc trên cạnh.

Ví dụ:

Nhập	In ra
5 2 1 1 2 3 4 2 3 3 5 5 1 1 3 3 2 2 5 4	3 3

Kiểm tra: nhập

8 3
0 0
-5 2
3 -1
3 3
7 7
-2 -2
1 1
3 0
-3 -3 3 3
0 0 10 10
-10 1 -1 5

Xem đáp số

6
5
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 5. Biến thể

Bài 17. Bảng có cập nhật

Bảng m hàng, n cột ban đầu toàn 0. Dòng đầu có m, n, q (1 ≤ m, n ≤ 1000, 1 ≤ q ≤ 10⁵), q dòng sau mỗi dòng là 1 r c v (cộng v vào ô (r, c), |v| ≤ 10⁶) hoặc 2 r1 c1 r2 c2 (hỏi tổng hình chữ nhật từ (r1, c1) đến (r2, c2)). In ra đáp số các câu hỏi loại 2.

Ví dụ:

Nhập	In ra
3 3 4 1 1 1 5 1 2 3 2 2 1 1 2 3 2 2 2 3 3	7 2

Kiểm tra: nhập

4 5 6
1 1 1 3
1 4 5 -2
1 2 3 7
2 1 1 4 5
1 1 1 -3
2 1 1 2 3

Xem đáp số

8
7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Dãy con tăng dài nhất

Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra độ dài lớn nhất của một dãy con (không cần liên tiếp) tăng ngặt.

Ví dụ:

Nhập	In ra
8 3 1 4 1 5 9 2 6	4

Kiểm tra: nhập

12
10 -3 7 7 2 8 -1 9 4 5 6 1

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Nghịch thế khi xoay vòng

Cho một hoán vị p của 1, 2, …, n. Mỗi lần xoay, chuyển số đầu tiên xuống cuối. Dòng đầu có n (1 ≤ n ≤ 2 × 10⁵), dòng thứ hai có p. In ra số nghịch thế nhỏ nhất trong n dãy: dãy ban đầu và n - 1 dãy sau từng lần xoay.

Ví dụ:

Nhập	In ra
4 3 4 1 2	0

Kiểm tra: nhập

8
5 7 2 8 1 3 6 4

Xem đáp số

7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Đoạn có tổng không quá S, có số âm

Dòng đầu có n, S (1 ≤ n ≤ 2 × 10⁵, |S| ≤ 10¹⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹, có thể âm). In ra số đoạn liên tiếp có tổng không quá S.

Ví dụ:

Nhập	In ra
4 2 3 -1 2 -4	8

Kiểm tra: nhập

10 0
5 -3 -3 4 1 -6 2 2 -1 0

Xem đáp số

32

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.