Fenwick Tree

Mỗi ô giữ một khúc dài lowbit

Ta cần một mảng $a_1, \dots, a_n$ hỗ trợ hai thao tác: update(pos, val) tăng $a_{pos}$ thêm $val$ (có thể âm), và get(pos) trả về $a_1 + \dots + a_{pos}$, bằng 0 khi $pos = 0$. Tổng đoạn $[l, r]$ là $\mathrm{get}(r) - \mathrm{get}(l-1)$; phép gán $a_k \leftarrow u$ là update(k, u - a[k]). Có hai cách làm hiển nhiên, mỗi cách chậm một đầu: giữ nguyên mảng thì sửa $O(1)$ nhưng hỏi tiền tố $O(n)$; giữ mảng tổng tiền tố thì hỏi $O(1)$ nhưng sửa một phần tử làm mọi tiền tố phía sau đổi theo, $O(n)$. Cây Fenwick chọn lối ở giữa: mỗi ô giữ tổng của một khúc, độ dài các khúc là $1, 2, 4, 8, \dots$, sao cho mỗi tiền tố ghép được từ ít khúc và mỗi phần tử nằm trong ít khúc, cả hai con số đều $O(\log n)$.

Với số nguyên dương $i$, $\mathrm{lowbit}(i)$ là giá trị của bit 1 thấp nhất trong cách viết nhị phân của $i$: $12 = 1100_2$ có $\mathrm{lowbit}(12) = 4$, $7 = 111_2$ có $\mathrm{lowbit}(7) = 1$, $40 = 101000_2$ có $\mathrm{lowbit}(40) = 8$. Trong C++ đó là i & -i (bài 14). Cây Fenwick là mảng $T_1, \dots, T_n$ (trong code là bit[1..n]), với

tức tổng của $\mathrm{lowbit}(i)$ phần tử kết thúc tại $i$. Chỉ số lẻ có $T_i = a_i$. Còn $T_2 = a_1 + a_2$, $T_6 = a_5 + a_6$, $T_8 = a_1 + \dots + a_8$, $T_{12} = a_9 + \dots + a_{12}$.

Truy vấn: ghép tiền tố từ các bit của $pos$. Để tính $\mathrm{get}(pos)$, bắt đầu từ ô $T_{pos}$: nó giữ $\mathrm{lowbit}(pos)$ phần tử cuối của tiền tố. Phần còn lại là tiền tố độ dài $pos - \mathrm{lowbit}(pos)$, xử lý đúng cách ấy. Mỗi bước xóa bit 1 thấp nhất, cho tới khi về 0. Với $13 = 1101_2$: $\mathrm{get}(13) = T_{13} + T_{12} + T_8$, ba khúc dài $1, 4, 8$ nối khít nhau. Số khúc bằng số bit 1, không quá $\lfloor \log_2 n \rfloor + 1$.

Cập nhật: sửa mọi ô phủ vị trí $pos$. Khi $a_{pos}$ tăng, ô $T_j$ phải tăng nếu khúc của nó chứa $pos$. Ô đầu tiên là $T_{pos}$; các ô còn lại nằm bên phải, và ta đi từ ô này sang ô phủ kế tiếp bằng cách cộng $\mathrm{lowbit}$. Với $n = 16$ và $pos = 5$, dãy ô là $5 \to 6 \to 8 \to 16$.

Vì sao đúng? Khúc của $T_k$ với $\mathrm{lowbit}(k) = 2^m$ là một khối căn lề $(c \cdot 2^m, (c+1) \cdot 2^m]$, nên hai khúc bất kỳ hoặc rời nhau hoặc lồng nhau. Đặt $b = \mathrm{lowbit}(i)$ và $j = i + b$. Không ô $k$ nào với $i < k < j$ phủ $i$, vì $\mathrm{lowbit}(k) = \mathrm{lowbit}(k - i) \le k - i$ nên khúc của $T_k$ bắt đầu sau $i$. Ô $T_j$ phủ $i$, vì $j$ chia hết cho $2b$ nên khúc của nó dài ít nhất $2b$. Và với $k > j$, $T_k$ phủ $i$ khi và chỉ khi $T_k$ phủ $j$, do tính lồng nhau. Vậy các ô phủ $i$ đúng là $i$, $j$, rồi các ô phủ $j$. Mỗi lần nhảy, $\mathrm{lowbit}$ ít nhất gấp đôi, nên có không quá $\log_2 n + 1$ ô.

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

Ví dụCộng Điểm, Hỏi Tiền Tố

Đề. Mảng $n \le 5 \cdot 10^6$ phần tử đánh số từ 0, ban đầu toàn 0. Xử lý $q \le 5 \cdot 10^6$ thao tác: + i delta cộng delta vào $a_i$; ? i in $a_0 + \dots + a_{i-1}$ (tổng rỗng là 0).

Lời giải. Đúng hai hàm trên, chỉ lệch chỉ số: phần tử $a_i$ của đề là ô $i + 1$ của cây, nên + i delta là update(i + 1, delta); còn “$i$ phần tử đầu” ứng với các ô $1..i$, nên ? i là get(i), và get(0) tự trả 0. Mảng bit $5 \cdot 10^6$ số ll là 40 MB. Dữ liệu cỡ $10^7$ số nên hai dòng tăng tốc là bắt buộc.

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

const ll N = 5e6 + 5;
ll n, q, bit[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    while (q--) {
        char op;
        ll i;
        cin >> op >> i;
        if (op == '+') {
            ll d;
            cin >> d;
            update(i + 1, d);
        } else cout << get(i) << '\n';
    }
}

Input5 8
? 0
+ 1 4
+ 3 -2
? 2
+ 0 7
? 1
? 4
? 5

Output0
4
7
9
9

Gán giá trị và dựng cây trong O(n)

Ba chỗ hay sai khi cài trọn vẹn. Một là chỉ số: cây chạy trên $1..n$. Hai là kiểu dữ liệu: tổng của $2 \cdot 10^5$ số cỡ $10^9$ lên tới $2 \cdot 10^{14}$, nên bit phải là long long. Ba là phép gán: cây chỉ biết cộng, nên muốn đặt $a_k = u$ ta giữ thêm mảng giá trị hiện tại a và gọi update(k, u - a[k]); a[k] = u;.

Dựng cây bằng $n$ lần update tốn $O(n \log n)$. Có cách dựng $O(n)$. Gọi $\mathrm{lowbit}(i) = 2^K$; các ô $c = i - 2^k$ với $k = 0, \dots, K - 1$ có khúc $(i - 2^{k+1}, i - 2^k]$, nối khít thành $(i - 2^K, i - 1]$, tức toàn bộ khúc của $T_i$ trừ $a_i$. Vậy

chẳng hạn $T_8 = a_8 + T_7 + T_6 + T_4$. Mỗi ô con $c$ thỏa $c + \mathrm{lowbit}(c) = i$, đúng là ô kế tiếp trong vòng cập nhật. Do đó gán bit[i] = a[i], rồi duyệt $i$ tăng dần và đẩy bit[i] lên ô $i + \mathrm{lowbit}(i)$: khi tới $i$ thì mọi ô con của nó, đều nhỏ hơn $i$, đã đẩy giá trị lên. Mỗi ô đẩy đúng một lần.

Ví dụTổng Đoạn Động

Đề. Cho $a_1..a_n$ và $q$ thao tác ($n, q \le 2 \cdot 10^5$, $1 \le a_i, u \le 10^9$): 1 k u gán $a_k = u$; 2 l r in $a_l + \dots + a_r$.

Lời giải. Dựng cây trong $O(n)$ như trên. Gán là cộng phần chênh lệch u - a[k] (có thể âm) rồi cập nhật a[k]; tổng đoạn là get(r) - get(l - 1). Bất biến: sau mỗi thao tác, get(i) bằng tổng tiền tố của mảng hiện tại. Mỗi thao tác không quá hai lần duyệt cây, mỗi lần 18 bước: cả bài cỡ $7 \cdot 10^6$ phép, so với $nq = 4 \cdot 10^{10}$ của cách ngây thơ.

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

const ll N = 2e5 + 5;
ll n, q, a[N], bit[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        bit[i] = a[i];
    }
    for (ll i = 1; i <= n; i++)
        if (i + (i & -i) <= n) bit[i + (i & -i)] += bit[i];
    while (q--) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            update(x, y - a[x]);
            a[x] = y;
        } else cout << get(y) - get(x - 1) << '\n';
    }
}

Input5 6
2 1 4 3 5
2 2 4
1 3 9
2 1 3
1 1 10
2 1 5
2 4 4

Output8
12
28
3

Cộng đoạn: mảng hiệu đặt vào cây

Đổi bài toán: thao tác cộng $v$ vào mọi $a_l..a_r$, và câu hỏi là giá trị một phần tử $a_k$. Dùng mảng hiệu của bài 02, $d_i = a_i - a_{i-1}$ với $a_0 = 0$. Cộng đoạn chỉ đổi hai ô, $d_l \mathrel{+}= v$ và $d_{r+1} \mathrel{-}= v$, còn $a_k = d_1 + \dots + d_k$ là một get. Ở bài 02 ta phải đọc hết thao tác rồi cộng dồn một lần; đặt $d$ vào cây Fenwick thì hỏi $a_k$ lúc nào cũng được: update(l, v); update(r + 1, -v); rồi $a_k$ = get(k). Khi $r = n$, ô $n + 1$ nằm ngoài cây và vòng lặp tự không chạy.

Còn khi cần tổng đoạn sau những lần cộng đoạn thì sao? Thay $a_i = \sum_{j \le i} d_j$ vào tổng $S(x) = a_1 + \dots + a_x$:

Đổi thứ tự lấy tổng vì $d_j$ góp mặt trong $a_j, \dots, a_x$, tức $x - j + 1$ lần. Chẳng hạn với $x = 3$: $S(3) = d_1 + (d_1 + d_2) + (d_1 + d_2 + d_3) = 3d_1 + 2d_2 + d_3$, đúng bằng $4(d_1 + d_2 + d_3) - (1 \cdot d_1 + 2 \cdot d_2 + 3 \cdot d_3)$. Hai tổng cuối là hai tiền tố: một trên cây $B_1$ giữ $d_j$, một trên cây $B_2$ giữ $j \cdot d_j$. Mỗi lần cộng đoạn sửa cả hai cây tại $l$ và $r + 1$, và tổng đoạn là $S(r) - S(l-1)$.

Ví dụCộng Đoạn, Tính Tổng

Đề. Có $T \le 10$ test, mỗi test một mảng $n \le 10^5$ phần tử ban đầu toàn 0 và $q \le 10^5$ thao tác: 0 l r v cộng $v$ vào $a_l..a_r$; 1 l r in $a_l + \dots + a_r$.

Lời giải. Dùng hai cây như ở trên: cộng $v$ vào đoạn $[l, r]$ thành bốn lần cập nhật điểm, và tổng tiền tố $a_1 + \dots + a_x$ bằng $(x + 1)\,B_1(x) - B_2(x)$.

Bước 1: một hàm cập nhật cho cả hai cây. Hai cây là hai mảng b1, b2; truyền mảng làm tham số để khỏi viết hai bản update, get giống hệt nhau.

void update(ll b[], ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) b[pos] += val;
}

ll get(ll b[], ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += b[pos];
    return res;
}

Bước 2: cộng đoạn và tổng tiền tố. add(l, r, v) ghi $+v$ tại $l$ và $-v$ tại $r + 1$ vào cây hiệu $B_1$, đồng thời ghi $v \cdot l$ và $-v \cdot (r + 1)$ vào $B_2$. pre(x) ghép hai cây theo công thức trên; tổng đoạn là pre(r) - pre(l - 1).

void add(ll l, ll r, ll v) {
    update(b1, l, v);
    update(b2, l, v * l);
    update(b1, r + 1, -v);
    update(b2, r + 1, -v * (r + 1));
}

ll pre(ll x) {
    return (x + 1) * get(b1, x) - get(b2, x);
}

Bước 3: xóa cây giữa các test. Hai cây là mảng toàn cục, nên dữ liệu của test trước còn nằm đó. Xóa $n + 1$ ô đầu là đủ, vì test này chỉ đụng tới các ô $1..n$ (ô $r + 1 = n + 1$ nằm ngoài cây và vòng update không ghi vào).

for (ll i = 0; i <= n; i++) b1[i] = b2[i] = 0;

Tổng tới cỡ $10^5 \cdot 10^5 \cdot 10^7 = 10^{17}$, vừa ll. Với test đầu, sau hai lần cộng mảng là $(2, 5, 3, 3, 0)$ và tổng $[2, 5]$ bằng 11.

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

const ll N = 1e5 + 5;
ll t, n, q, b1[N], b2[N];

void update(ll b[], ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) b[pos] += val;
}

ll get(ll b[], ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += b[pos];
    return res;
}

void add(ll l, ll r, ll v) {
    update(b1, l, v);
    update(b2, l, v * l);
    update(b1, r + 1, -v);
    update(b2, r + 1, -v * (r + 1));
}

ll pre(ll x) {
    return (x + 1) * get(b1, x) - get(b2, x);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n >> q;
        for (ll i = 0; i <= n; i++) b1[i] = b2[i] = 0;
        while (q--) {
            ll type, l, r;
            cin >> type >> l >> r;
            if (type == 0) {
                ll v;
                cin >> v;
                add(l, r, v);
            } else cout << pre(r) - pre(l - 1) << '\n';
        }
    }
}

+12 dòngInput2
5 5
1 1 5
0 2 4 3
1 1 3
0 1 2 2
1 2 5
4 4
0 1 4 1
0 2 3 4
1 1 4
1 2 2

Output0
6
11
12
5

Mỗi thao tác tốn bốn lần cập nhật hoặc bốn lần truy vấn, mỗi lần $O(\log n)$.

Fenwick đếm: chỉ số là giá trị

Từ đầu bài, chỉ số là vị trí. Ta cũng có thể lấy chỉ số là giá trị: ô của giá trị $v$ đếm số phần tử bằng $v$ đang có trong một đa tập. Chèn $v$ là update(v, 1), xóa là update(v, -1), và get(v) là số phần tử $\le v$. Mọi câu hỏi kiểu “đã thấy bao nhiêu phần tử nhỏ hơn, lớn hơn, hay nằm trong khoảng nào” đều thành một hay hai lần get. Đây là cách dùng phổ biến nhất của cây trong đề thi.

Giá trị tới $10^9$ thì không thể dành $10^9$ ô. Nếu biết trước mọi giá trị có thể xuất hiện (đọc hết input trước, kể cả giá trị trong các lệnh đổi), ta nén tọa độ như ở bài 03: sắp xếp, bỏ trùng thành mảng vals, rồi thay mỗi giá trị bằng hạng $1..m$ của nó, lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1. Nén giữ nguyên thứ tự nên mọi phép so sánh $<$ và $\le$ vẫn đúng.

Phần tử thứ $k$. Bài toán ngược: biết $k$, tìm giá trị nhỏ thứ $k$ của đa tập, tức chỉ số nhỏ nhất $p$ có $\mathrm{get}(p) \ge k$. Chặt nhị phân trên $p$ rồi gọi get tốn $O(\log n \cdot \log n)$; đi thẳng xuống trong cây chỉ $O(\log n)$. Cho $p$ chạy từ 0; với $2^e$ lần lượt là lũy thừa của 2 lớn nhất không vượt $n$, rồi giảm dần tới 1: nếu $p + 2^e \le n$ và $T_{p + 2^e} < k$ thì nhảy $p \mathrel{+}= 2^e$ và trừ $T_p$ khỏi $k$. Cuối cùng đáp án là $p + 1$. Khi xét bước $2^e$, $p$ là bội của $2^{e+1}$ nên khúc của ô $p + 2^e$ đúng là $(p, p + 2^e]$, và đây là chặt nhị phân trên từng bit của đáp án. Cách này cần giá trị trong cây không âm.

Chương trình dưới giữ một đa tập các số trong $[1, n]$: + x chèn $x$, ? x in phần tử nhỏ thứ $x$, - x xóa phần tử nhỏ thứ $x$ và in giá trị bị xóa.

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

const ll N = 1e5 + 5;
ll n, q, bit[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}

ll kth(ll k) {
    ll p = 0;
    for (ll e = __lg(n); e >= 0; e--)
        if (p + (1LL << e) <= n && bit[p + (1LL << e)] < k) {
            p += 1LL << e;
            k -= bit[p];
        }
    return p + 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    while (q--) {
        char op;
        ll x;
        cin >> op >> x;
        if (op == '+') update(x, 1);
        else if (op == '?') cout << kth(x) << '\n';
        else {
            ll v = kth(x);
            cout << v << '\n';
            update(v, -1);
        }
    }
}

Input10 9
+ 7
+ 3
+ 7
+ 5
? 2
? 3
- 2
? 2
? 3

Output5
7
5
7
7

Đa tập có $\{3, 5, 7, 7\}$ nên phần tử nhỏ thứ 2 và thứ 3 là 5 và 7. Lệnh - 2 xóa số 5, còn $\{3, 7, 7\}$ nên hai câu hỏi sau cùng cho 7.

Ví dụNhững Cặp Đảo Thứ Tự

Đề. Đếm số cặp $u < v$ có $a_u > a_v$ trong dãy $n \le 6 \cdot 10^4$ số nguyên $1 \le a_i \le 6 \cdot 10^4$; hai số bằng nhau không tạo nghịch thế.

Lời giải. Mỗi nghịch thế có đúng một đầu phải, nên đếm theo đầu phải. Quét $i$ từ trái sang và giữ trong cây Fenwick, theo giá trị, các phần tử đã quét. Khi tới phần tử thứ $i$ (đếm từ 0), cây chứa đúng $i$ phần tử đứng trước, trong đó get(a[i]) phần tử không lớn hơn $a_i$, nên $i - \mathrm{get}(a_i)$ phần tử lớn hơn hẳn. Phải hỏi trước khi thêm chính $a_i$, nếu không $a_i$ tự đếm mình. Giá trị chỉ tới $6 \cdot 10^4$ nên dùng thẳng làm chỉ số; giá trị tới $10^9$ thì nén trước. Với ví dụ $4, 1, 3, 2, 5, 2$: các lượt cộng $0, 1, 1, 2, 0, 3$, tổng 7; số 2 cuối không đếm số 2 đứng trước vì bằng nó.

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

const ll M = 6e4;
ll n, bit[M + 5];

void update(ll pos, ll val) {
    for (; pos <= M; pos += pos & -pos) bit[pos] += val;
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res += bit[pos];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll x;
        cin >> x;
        ans += i - get(x);
        update(x, 1);
    }
    cout << ans << '\n';
}

Input6
4
1
3
2
5
2

Output7

Khi nào Fenwick không đủ

Công thức $\mathrm{get}(r) - \mathrm{get}(l-1)$ cần phép toán có phép ngược, nên cây hợp với cộng, XOR và đếm, giống điều kiện của tổng tiền tố ở bài 02. Với min và max thì không: $\min(a_1..a_r)$ không cho biết $\min(a_l..a_r)$.

Có một ngoại lệ hữu ích. Nếu mọi cập nhật chỉ làm giá trị tăng lên và ta chỉ hỏi tiền tố, thay phép cộng bằng max: bit[pos] = max(bit[pos], val) trong vòng cập nhật, và lấy max trong vòng truy vấn. Đây là cách giải nhiều bài quy hoạch động theo giá trị. Nhưng nếu giá trị có thể giảm đi, hoặc cần max trên đoạn $[l, r]$ bất kỳ, hoặc gán cả một đoạn, thì phải dùng cây phân đoạn (bài 17).

Cây có bản hai chiều bằng hai vòng lặp lồng nhau, mỗi thao tác $O(\log n \cdot \log n)$ (bài 45). Với nhiều test, đặt lại $n + 1$ ô cho mỗi test, nên chỉ ổn khi tổng $n$ qua các test bị chặn. So với cây phân đoạn, Fenwick ngắn hơn và thường chạy nhanh hơn, đổi lại nó chỉ làm được các việc kể trên.

Ví dụDãy Tăng Có Trọng Số

Đề. Có $n \le 2 \cdot 10^5$ phần tử, phần tử $i$ có chiều cao $h_i$ (một hoán vị của $1..n$) và trọng số $b_i \le 10^9$. Chọn một dãy con có chiều cao tăng nghiêm ngặt với tổng trọng số lớn nhất.

Lời giải. Quy hoạch động như dãy con tăng của bài 12: $\mathrm{dp}_i = b_i + \max \mathrm{dp}_j$ trên các $j < i$ có $h_j < h_i$, nhưng tìm max kiểu duyệt mọi $j$ là $O(n^2)$. Quét $i$ tăng dần và giữ một cây Fenwick max theo chiều cao: ô của chiều cao $h$ ghi $\mathrm{dp}$ của phần tử đã quét có chiều cao đó. Khi tới $i$, các phần tử đã quét đều đứng trước $i$, nên $\max \mathrm{dp}_j$ cần tìm là max tiền tố trên chiều cao $h_i - 1$. Mỗi ô chỉ được ghi một lần và giá trị trong cây chỉ tăng, đúng ngoại lệ cho phép dùng max. Cả bài $O(n \log n)$; tổng tới $2 \cdot 10^{14}$.

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

const ll N = 2e5 + 5;
ll n, h[N], b[N], bit[N];

void update(ll pos, ll val) {
    for (; pos <= n; pos += pos & -pos) bit[pos] = max(bit[pos], val);
}

ll get(ll pos) {
    ll res = 0;
    for (; pos > 0; pos -= pos & -pos) res = max(res, bit[pos]);
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> h[i];
    for (ll i = 0; i < n; i++) cin >> b[i];
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll dp = get(h[i] - 1) + b[i];
        update(h[i], dp);
        ans = max(ans, dp);
    }
    cout << ans << '\n';
}

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

Output15