Segment Tree

Chia đôi dãy, mỗi đoạn một nút

Ý tưởng là tính trước đáp án cho một số đoạn được chọn khéo: đủ ít để sửa nhanh khi một phần tử đổi, đủ nhiều để ghép thành mọi đoạn hỏi. Cách chọn là chia đôi. Đoạn $[l, r]$ với $l < r$ tách tại $mid = \lfloor (l + r)/2 \rfloor$ thành $[l, mid]$ và $[mid + 1, r]$, cứ thế tới khi đoạn chỉ còn một phần tử. Các đoạn ấy xếp thành một cây nhị phân: nút quản lý một đoạn, gốc quản lý $[1, n]$, hai con của một nút quản lý hai nửa của nó, lá quản lý đúng một phần tử. Mỗi nút lưu min của đoạn mình quản lý. Cây có $2n - 1$ nút. Hình dưới là cây của $a = (5, 2, 7, 3, 8, 1, 6, 4)$.

Hỏi đoạn $[2, 7]$. Ta lấy các nút lớn nhất nằm trọn trong đoạn hỏi: $[2,2]$, $[3,4]$, $[5,6]$ và $[7,7]$. Bốn đoạn này rời nhau và ghép lại đúng bằng $[2, 7]$, nên đáp án là $\min(2, 3, 1, 6) = 1$. Sửa một phần tử. Gán $a_6 \gets 9$ chỉ làm đổi các nút có đoạn chứa vị trí 6, tức một đường từ lá lên gốc: $[6,6]$, $[5,6]$, $[5,8]$, $[1,8]$. Ta tính lại từng nút từ dưới lên bằng min của hai con; mọi nút khác giữ nguyên.

Cài đặt. Quy ước cả bài: đánh số từ 1, đoạn đóng $[l, r]$, gốc có số hiệu 1, hai con của nút id là id * 2 và id * 2 + 1, mảng st có $4n$ ô. Ba hàm build, update, get nhận số hiệu nút cùng đoạn $[l, r]$ mà nút ấy quản lý. Hàm get(id, l, r, u, v) hỏi đoạn $[u, v]$ và chỉ có ba trường hợp: đoạn của nút rời đoạn hỏi thì trả một giá trị trung hòa ($10^{18}$ với min, lớn hơn mọi giá trị thật); nằm trọn thì trả st[id] và dừng; còn lại thì hỏi hai con rồi gộp. Hàm update đi xuống đúng một con chứa vị trí cần sửa, rồi tính lại st[id] từ hai con khi quay lên; dòng tính lại đó giữ cho mọi nút trên đường đi đúng.

Vì sao mỗi thao tác chỉ tốn logarit. Mỗi lần chia đôi, độ dài đoạn giảm còn nhiều nhất một nửa làm tròn lên, nên cây có tối đa $\lceil \log_2 n \rceil + 1$ tầng, với $n = 2 \cdot 10^5$ là 19. Cập nhật ghé đúng một nút mỗi tầng. Với truy vấn, gọi nút là cắt nếu đoạn của nó giao đoạn hỏi nhưng không nằm trọn; chỉ nút cắt mới gọi xuống hai con. Một nút cắt có cả phần tử trong và ngoài đoạn hỏi, mà đoạn của nó liền mạch, nên nó phải chứa biên trái hoặc biên phải của đoạn hỏi. Các nút cùng tầng rời nhau, nên mỗi tầng có không quá hai nút cắt, sinh không quá bốn con ở tầng kế tiếp: truy vấn ghé tối đa $4 \cdot 19 = 76$ nút.

Bộ nhớ. Số hiệu các nút không liền nhau: nút ở tầng $d$ có số hiệu trong $[2^d, 2^{d+1})$ và tầng cuối thường còn khoảng trống. Số hiệu lớn nhất không vượt $2^{h+1} - 1$ với $h = \lceil \log_2 n \rceil$, mà $2^{h-1} < n$ nên $2^{h+1} < 4n$. Mảng $4n$ ô luôn đủ, còn $2n$ ô có thể thủng.

Ví dụGiá Trị Thấp Nhất

Đề. Dãy $n \le 2 \cdot 10^5$ ô, $q \le 2 \cdot 10^5$ yêu cầu: 1 k u gán ô $k$ bằng $u$; 2 l r in min của các ô từ $l$ đến $r$.

Lời giải. Đúng cây min ở trên: nút $[l, r]$ lưu min của các ô trong đoạn, gộp hai con bằng min. Ba hàm theo đúng khung đã học.

Bước 1: dựng cây. Lá lưu chính ô đó; nút trong lưu min của hai con, tính sau khi đã dựng hai con.

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

Bước 2: gán một ô. Đi xuống đúng một nhánh chứa pos, gán ở lá, rồi tính lại min trên đường đi lên. Chỉ $O(\log n)$ nút bị đổi.

void update(ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        st[id] = val;
        return;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

Bước 3: hỏi min đoạn. Nút nằm ngoài $[u, v]$ trả về phần tử trung hòa $10^{18}$, không ảnh hưởng phép min; nút nằm trọn trong $[u, v]$ trả về giá trị đã lưu; còn lại hỏi hai con.

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return 1e18;
    if (u <= l && r <= v) return st[id];
    ll mid = (l + r) >> 1;
    return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

Với ví dụ, cả dãy $(7, 2, 9, 2, 6)$ có min 2; sau khi gán $a_2 = 8$, đoạn $[1, 3]$ có min 7.

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

const ll N = 2e5 + 5;
ll n, q, a[N], st[4 * N];

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

void update(ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        st[id] = val;
        return;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return 1e18;
    if (u <= l && r <= v) return st[id];
    ll mid = (l + r) >> 1;
    return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

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

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

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

Output2
7
6
10

Thời gian $O((n + q) \log n)$, khoảng $1{,}5 \cdot 10^7$ lần ghé nút; mảng st cần $4n$ ô.

Nút lưu gì cũng được, miễn gộp được

Nhìn lại ba hàm trên: chữ min xuất hiện đúng ba chỗ, là giá trị của lá, cách tính nút từ hai con và giá trị trả về cho đoạn rời. Mọi thứ còn lại chỉ nói về hình dạng cây. Thay ba chỗ ấy bằng $0$ và phép cộng thì ta có cây cho tổng; bằng $0$ và $\gcd$ thì có cây cho ước chung lớn nhất; tương tự cho max, XOR, hay đếm số phần tử thỏa một tính chất.

Tổng quát, mỗi nút lưu một tóm tắt (summary) của đoạn nó quản lý, với hai điều kiện. Thứ nhất, tóm tắt của một đoạn tính được từ tóm tắt của hai nửa bằng một hàm combine(a, b), trong đó $a$ là nửa trái và $b$ là nửa phải. Thứ hai, có một tóm tắt của đoạn rỗng (phần tử trung hòa) mà gộp với nó không đổi gì. Khi đó cả ba hàm giữ nguyên, chỉ đổi min thành combine. Truy vấn ghép các nút nằm trọn trong đoạn hỏi theo thứ tự từ trái sang phải.

Không phải đại lượng nào cũng làm tóm tắt được. Điều kiện thứ nhất đòi tóm tắt của đoạn cha suy ra được từ tóm tắt của hai con chỉ bằng thông tin đã lưu. Với tổng, min, gcd, điều đó đúng. Với trung vị thì sai. Khi một đại lượng không gộp được một mình, cách chữa thường là lưu kèm vài đại lượng phụ cho đủ.

Một điều nữa dễ bỏ sót: combine không cần giao hoán, nhưng thứ tự đối số có nghĩa. Trong get, lời gọi combine(get(trái), get(phải)) luôn đặt nửa trái trước, nên thứ tự vị trí được giữ nguyên. Với min, tổng, gcd chuyện này không đáng bận tâm. Với phép gộp như “đoạn con có tổng lớn nhất” ở ví dụ thứ hai dưới đây, đảo thứ tự cho kết quả sai.

Ví dụMức Nhỏ Nhất Và Số Lần

Đề. Mảng $n \le 10^5$ phần tử đánh số từ 0, $m \le 10^5$ thao tác: 1 i v gán $a_i = v$; 2 l r in min trên đoạn nửa mở $[l, r)$ cùng số vị trí đạt min đó.

Lời giải. Mỗi nút lưu cặp (min, số lần đạt min). Ba hàm build, update, get giữ nguyên khung của ví dụ trước; chỉ thay phép min bằng hàm gộp cặp và phần tử trung hòa.

Bước 1: gộp hai cặp. Nếu min của hai nửa khác nhau, mọi vị trí đạt min của cả đoạn nằm ở nửa có min nhỏ hơn, nên giữ nguyên cặp của nửa ấy. Nếu bằng nhau, cả hai nửa đều đóng góp: cộng hai số lần.

pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y) {
    if (x.first < y.first) return x;
    if (y.first < x.first) return y;
    return {x.first, x.second + y.second};
}

Bước 2: lá và phần tử trung hòa. Lá của ô giá trị $v$ là $(v, 1)$, ở cả build lẫn update. Nút ngoài đoạn hỏi trả về $(10^{18}, 0)$: min lớn hơn mọi giá trị thật nên combine luôn chọn bên kia, và số lần 0 không làm sai tổng.

pair<ll, ll> get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return {1e18, 0};
    if (u <= l && r <= v) return st[id];
    ll mid = (l + r) >> 1;
    return combine(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

Bước 3: đổi chỉ số của đề. Cây đánh số từ 1, đề đánh số từ 0 với đoạn nửa mở: phần tử $a_i$ là vị trí $i + 1$, và đoạn $[l, r)$ là các vị trí $l + 1..r$.

if (t == 1) update(1, 1, n, x + 1, y);
else {
    pair<ll, ll> res = get(1, 1, n, x + 1, y);
    cout << res.first << ' ' << res.second << '\n';
}

Với ví dụ, $(4, 1, 1, 3, 2)$ có min 1 xuất hiện 2 lần.

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

const ll N = 1e5 + 5;
ll n, m, a[N];
pair<ll, ll> st[4 * N];

pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y) {
    if (x.first < y.first) return x;
    if (y.first < x.first) return y;
    return {x.first, x.second + y.second};
}

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = {a[l], 1};
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
}

void update(ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        st[id] = {val, 1};
        return;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
}

pair<ll, ll> get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return {1e18, 0};
    if (u <= l && r <= v) return st[id];
    ll mid = (l + r) >> 1;
    return combine(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

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

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) update(1, 1, n, x + 1, y);
        else {
            pair<ll, ll> res = get(1, 1, n, x + 1, y);
            cout << res.first << ' ' << res.second << '\n';
        }
    }
}

Input5 5
4 1 1 3 2
2 0 5
1 2 5
2 0 3
1 0 1
2 0 4

Output1 2
1 1
1 2

Mỗi thao tác $O(\log n)$.

Ví dụTổng Đoạn Liên Tiếp

Đề. Dãy $n \le 2 \cdot 10^5$ số, $|a_i| \le 10^9$, và $m \le 2 \cdot 10^5$ lần gán $a_k \gets x$. Sau mỗi lần gán, in tổng lớn nhất của một đoạn con liên tiếp của cả dãy (được chọn đoạn rỗng, tổng 0).

Lời giải. Chỉ lưu đoạn con tốt nhất của mỗi nút thì chưa gộp được: đoạn tốt nhất của hai nửa ghép lại có thể vắt qua ranh giới, khi đó nó là một hậu tố của nửa trái nối với một tiền tố của nửa phải. Vậy mỗi nút lưu bốn số: tổng cả đoạn sum, tiền tố lớn nhất pre, hậu tố lớn nhất suf, đoạn con lớn nhất best; ba số cuối cho phép rỗng nên không âm. Gộp nửa trái $a$ với nửa phải $b$:

Một tiền tố của đoạn ghép hoặc nằm gọn trong nửa trái, hoặc là cả nửa trái rồi tới một tiền tố của nửa phải; hậu tố đối xứng; đoạn con thì nằm gọn một bên hoặc cắt ranh giới. Phép gộp không giao hoán: $(2, -1)$ ghép $(4, -5)$ cho best 5, đổi chỗ thì ra 4.

Bước 1: nút và lá. Lá giá trị $x$ có tổng $x$, còn ba số kia là $\max(0, x)$: hoặc lấy chính ô đó, hoặc lấy đoạn rỗng.

struct Node {
    ll sum, pre, suf, best;
};

Node leaf(ll x) {
    return {x, max(0LL, x), max(0LL, x), max(0LL, x)};
}

Bước 2: gộp. Viết đúng ba công thức trên, tổng thì cộng hai nửa. Thứ tự tham số quan trọng: a là nửa trái, b là nửa phải.

Node combine(Node a, Node b) {
    return {a.sum + b.sum, max(a.pre, a.sum + b.pre), max(b.suf, b.sum + a.suf),
            max({a.best, b.best, a.suf + b.pre})};
}

Bước 3: sửa rồi đọc gốc. build và update giữ khung quen thuộc, lá dùng leaf, nút trong dùng combine. Bài chỉ hỏi cả dãy, nên đáp án sau mỗi lần gán là best ở gốc, không cần hàm get.

update(1, 1, n, k, x);
cout << st[1].best << '\n';

Tổng tới $2 \cdot 10^{14}$, vừa ll.

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

struct Node {
    ll sum, pre, suf, best;
};

const ll N = 2e5 + 5;
ll n, m, a[N];
Node st[4 * N];

Node leaf(ll x) {
    return {x, max(0LL, x), max(0LL, x), max(0LL, x)};
}

Node combine(Node a, Node b) {
    return {a.sum + b.sum, max(a.pre, a.sum + b.pre), max(b.suf, b.sum + a.suf),
            max({a.best, b.best, a.suf + b.pre})};
}

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = leaf(a[l]);
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
}

void update(ll id, ll l, ll r, ll pos, ll val) {
    if (l == r) {
        st[id] = leaf(val);
        return;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid) update(id * 2, l, mid, pos, val);
    else update(id * 2 + 1, mid + 1, r, pos, val);
    st[id] = combine(st[id * 2], st[id * 2 + 1]);
}

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

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        ll k, x;
        cin >> k >> x;
        update(1, 1, n, k, x);
        cout << st[1].best << '\n';
    }
}

Input5 4
-3 2 -1 4 -5
1 -2
5 3
2 -6
4 -8

Output5
8
7
3

Mỗi lần gán $O(\log n)$; đọc đáp án $O(1)$.

Đi xuống cây để tìm vị trí

Có bài không hỏi giá trị của một đoạn mà hỏi vị trí. Ví dụ: dãy bit $b_1, \dots, b_n$, thao tác đảo một bit, và câu hỏi “bit 1 thứ $k$ tính từ trái nằm ở vị trí nào”. Chặt nhị phân trên vị trí cần một truy vấn $O(\log n)$ cho mỗi bước chặt, tổng $O(\log n \cdot \log n)$. Cây cho phép bỏ lớp chặt bên ngoài.

Mỗi nút lưu số bit 1 trong đoạn của nó. Đi từ gốc, giữ bất biến “đáp án là bit 1 thứ $k$ bên trong đoạn của nút hiện tại”. Tại một nút: nếu con trái có ít nhất $k$ bit 1 thì đi trái, giữ nguyên $k$; ngược lại bỏ qua mọi bit 1 của con trái, trừ chúng khỏi $k$ rồi đi phải. Mỗi bước xuống một tầng; tới lá thì đó là đáp án. Điều kiện bắt đầu là gốc có ít nhất $k$ bit 1.

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

const ll N = 1e5 + 5;
ll n, q, b[N], st[4 * N];

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = b[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void flip(ll id, ll l, ll r, ll pos) {
    if (l == r) {
        st[id] ^= 1;
        return;
    }
    ll mid = (l + r) >> 1;
    if (pos <= mid) flip(id * 2, l, mid, pos);
    else flip(id * 2 + 1, mid + 1, r, pos);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

ll kth(ll id, ll l, ll r, ll k) {
    if (l == r) return l;
    ll mid = (l + r) >> 1;
    if (st[id * 2] >= k) return kth(id * 2, l, mid, k);
    return kth(id * 2 + 1, mid + 1, r, k - st[id * 2]);
}

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

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> b[i];
    build(1, 1, n);
    while (q--) {
        ll t, x;
        cin >> t >> x;
        if (t == 1) flip(1, 1, n, x);
        else cout << (st[1] < x ? -1 : kth(1, 1, n, x)) << '\n';
    }
}

Input10 7
0 1 1 0 0 1 0 1 1 0
2 1
2 4
2 6
1 2
2 2
1 10
2 5

Output2
8
-1
6
10

Các bit 1 ban đầu nằm ở vị trí $2, 3, 6, 8, 9$, nên bit thứ 1 ở vị trí 2, bit thứ 4 ở vị trí 8, và không có bit thứ 6. Lỗi hay gặp nhất là quên trừ số bit 1 của con trái khi sang phải: khi đó $k$ vẫn tính cả những bit 1 đã bỏ qua và ta lạc sang nhánh sai. Cùng khuôn đó dùng cho “vị trí đầu tiên có $a_i \ge x$” trên cây lưu max: sang trái nếu max của con trái $\ge x$, ngược lại sang phải. Nếu chỉ số của cây là giá trị và nút đếm số lần xuất hiện, cùng cách đi xuống ấy tìm được phần tử nhỏ thứ $k$ của một tập đang thay đổi.

Ví dụPhân Bổ Phòng

Đề. Có $n \le 2 \cdot 10^5$ khách sạn, khách sạn $i$ còn $h_i$ phòng. Lần lượt $m$ đoàn đến, đoàn $j$ cần $r_j$ phòng và được xếp vào khách sạn có chỉ số nhỏ nhất còn ít nhất $r_j$ phòng (rồi khách sạn đó bớt $r_j$ phòng); không có thì in 0.

Lời giải. Cây lưu max số phòng còn trống của mỗi đoạn khách sạn. Nếu max ở gốc nhỏ hơn $r_j$ thì không khách sạn nào đủ chỗ, in 0. Ngược lại đi xuống từ gốc: khách sạn đầu tiên đủ chỗ nằm bên trái khi và chỉ khi bên trái có ít nhất một khách sạn đủ chỗ, tức max của con trái $\ge r_j$. Tới lá là đúng khách sạn cần tìm.

Bước 1: dựng cây max. Như cây min, chỉ đổi min thành max.

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = h[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

Bước 2: đi xuống tìm và trừ luôn. walk vừa tìm vừa sửa trong một lượt: rẽ trái nếu con trái đủ chỗ, ngược lại rẽ phải; tới lá thì trừ $x$ phòng và trả về chỉ số khách sạn; trên đường quay lên tính lại max. Lời gọi chỉ diễn ra khi gốc đủ chỗ, nên nhánh phải luôn đủ chỗ mỗi khi nhánh trái không đủ.

ll walk(ll id, ll l, ll r, ll x) {
    if (l == r) {
        st[id] -= x;
        return l;
    }
    ll mid = (l + r) >> 1, res;
    if (st[id * 2] >= x) res = walk(id * 2, l, mid, x);
    else res = walk(id * 2 + 1, mid + 1, r, x);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
    return res;
}

Bước 3: từng đoàn. Kiểm max ở gốc trước, đủ chỗ mới gọi walk.

cout << (st[1] < x ? 0 : walk(1, 1, n, x)) << ' ';

Với ví dụ, đoàn cần 3 phòng đi tới khách sạn 3 vì khách sạn 1 lúc đó chỉ còn 1 phòng.

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

const ll N = 2e5 + 5;
ll n, m, h[N], st[4 * N];

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = h[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

ll walk(ll id, ll l, ll r, ll x) {
    if (l == r) {
        st[id] -= x;
        return l;
    }
    ll mid = (l + r) >> 1, res;
    if (st[id * 2] >= x) res = walk(id * 2, l, mid, x);
    else res = walk(id * 2 + 1, mid + 1, r, x);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
    return res;
}

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

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> h[i];
    build(1, 1, n);
    while (m--) {
        ll x;
        cin >> x;
        cout << (st[1] < x ? 0 : walk(1, 1, n, x)) << ' ';
    }
    cout << '\n';
}

Input4 5
3 1 4 2
2 3 1 4 2

Output1 3 1 0 4

Mỗi đoàn đi một đường từ gốc tới lá: $O(\log n)$.

Cập nhật đoạn và thẻ lười

Thêm một loại thao tác: cộng $x$ vào mọi $a_i$ với $l \le i \le r$, và hỏi tổng đoạn. Cập nhật điểm cho từng vị trí tốn $O(n \log n)$ một thao tác. Ta nhớ rằng truy vấn chỉ ghép $O(\log n)$ nút nằm trọn trong đoạn; cập nhật cũng chỉ nên chạm tới đúng những nút đó. Một nút nằm trọn trong $[l, r]$ biết ngay tổng mới của mình: tổng cũ cộng $x$ nhân độ dài đoạn. Còn các nút bên dưới nó thì ta chưa sửa, và ta ghi nợ ở nút: “mọi phần tử ở dưới bị cộng thêm $x$, hai con chưa biết”. Khoản nợ ấy là một thẻ (tag). Chỉ khi một thao tác sau cần chui xuống con của nút này, ta mới trả nợ: chuyển thẻ cho hai con rồi xóa thẻ ở nút. Kỹ thuật này gọi là cập nhật lười (lazy propagation).

Hai mảng có ý nghĩa chính xác:

• st[id] là tổng đúng của đoạn, với điều kiện thẻ của mọi nút tổ tiên đã được đẩy xuống;
• lz[id] là số cần cộng vào mỗi phần tử của đoạn mà hai con chưa biết; phần cộng này st[id] đã chứa rồi.

Hàm apply(id, len, x) đặt thẻ $x$ lên một nút dài $len$: st[id] += x * len, lz[id] += x. Hàm down(id, l, r) đẩy thẻ của nút xuống hai con rồi xóa nó. Hai quy tắc: gặp nút nằm trọn thì đặt thẻ và dừng; gặp nút cắt thì đẩy thẻ trước khi xuống hai con, rồi tính lại st[id] từ hai con khi quay lên. Cả hai quy tắc áp dụng cho cập nhật lẫn truy vấn.

Chạy tay trên $a = (5, 2, 7, 3, 8, 1, 6, 4)$ với thao tác “cộng 3 vào $[2, 7]$”: hai nút $[3, 4]$ và $[5, 6]$ nằm trọn nên nhận thẻ $+3$, tổng thành $16$ và $15$; lá $[2,2]$ và $[7,7]$ cũng nằm trọn và thành $5$, $9$; các nút cắt tính lại từ con, gốc thành $54 = 36 + 6 \cdot 3$. Bốn lá $[3,3]$ tới $[6,6]$ chưa hề được chạm tới. Nếu sau đó hỏi tổng $[3, 3]$, đường đi qua $[3, 4]$ là nút cắt, nên thẻ $+3$ được đẩy xuống và lá $[3,3]$ trả về $7 + 3 = 10$.

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

const ll N = 2e5 + 5;
ll n, q, a[N], st[4 * N], lz[4 * N];

void build(ll id, ll l, ll r) {
    if (l == r) {
        st[id] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void apply(ll id, ll len, ll x) {
    st[id] += x * len;
    lz[id] += x;
}

void down(ll id, ll l, ll r) {
    if (!lz[id]) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, mid - l + 1, lz[id]);
    apply(id * 2 + 1, r - mid, lz[id]);
    lz[id] = 0;
}

void update(ll id, ll l, ll r, ll u, ll v, ll x) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        apply(id, r - l + 1, x);
        return;
    }
    down(id, l, r);
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v, x);
    update(id * 2 + 1, mid + 1, r, u, v, x);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return st[id];
    down(id, l, r);
    ll mid = (l + r) >> 1;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

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

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

Input8 5
5 2 7 3 8 1 6 4
2 1 8
1 2 7 3
2 1 8
2 3 4
2 5 8

Output36
54
16
28

Vì sao đúng. Mỗi lần đi từ một nút cắt xuống con, ta đã đẩy thẻ của nút cắt ấy, nên khi hàm chạm tới một nút bất kỳ thì mọi tổ tiên của nó đều đang có thẻ bằng 0, và st của nút đó là tổng đúng. Các nút được ghé giống hệt phần chứng minh trước, down chỉ tốn $O(1)$, nên cập nhật đoạn và truy vấn đều $O(\log n)$. Ba lỗi hay gặp: quên down trong hàm truy vấn (chạy đúng trên ví dụ ngắn nhưng sai khi một thẻ còn treo ở nút cắt), quên nhân với độ dài khi áp thẻ lên tổng, và quên tính lại st[id] sau hai lời gọi đệ quy ở update.

Ví dụDãy Công Tắc

Đề. Có $N \le 10^5$ đèn, ban đầu tắt, và $M \le 10^5$ thao tác: 0 S E đảo trạng thái mọi đèn từ $S$ tới $E$; 1 S E đếm số đèn đang bật trong đoạn đó.

Lời giải. Nút lưu số đèn bật trong đoạn. Thẻ là một cờ “đảo”: đảo cả một đoạn dài $len$ làm số đèn bật thành $len$ trừ số cũ, và hai lần đảo triệt tiêu nhau, nên thẻ chỉ cần một bit, hợp hai thẻ là XOR. Phần còn lại giống hệt cây cộng đoạn ở trên.

Bước 1: áp thẻ lên một nút. Biết độ dài đoạn của nút là đủ để cập nhật giá trị ngay, không cần xuống con.

void apply(ll id, ll len) {
    st[id] = len - st[id];
    lz[id] ^= 1;
}

Bước 2: đẩy thẻ xuống. Trước khi đi vào con, nếu nút còn thẻ thì áp nó cho hai con (độ dài $mid - l + 1$ và $r - mid$) rồi xóa thẻ ở nút.

void down(ll id, ll l, ll r) {
    if (!lz[id]) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, mid - l + 1);
    apply(id * 2 + 1, r - mid);
    lz[id] = 0;
}

Bước 3: đảo đoạn và đếm đoạn. Nút nằm trọn trong đoạn thì áp thẻ và dừng; nút cắt ngang thì đẩy thẻ, đi xuống hai con, rồi cộng lại. get cũng phải đẩy thẻ trước khi xuống con, vì giá trị ở con có thể chưa được cập nhật.

void update(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        apply(id, r - l + 1);
        return;
    }
    down(id, l, r);
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v);
    update(id * 2 + 1, mid + 1, r, u, v);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

Ban đầu mọi đèn tắt, mọi ô bằng 0, nên không cần build. Với ví dụ, sau hai lần đảo $[2, 5]$ rồi $[3, 6]$, chỉ đèn 2 và 6 sáng.

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

const ll N = 1e5 + 5;
ll n, m, st[4 * N], lz[4 * N];

void apply(ll id, ll len) {
    st[id] = len - st[id];
    lz[id] ^= 1;
}

void down(ll id, ll l, ll r) {
    if (!lz[id]) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, mid - l + 1);
    apply(id * 2 + 1, r - mid);
    lz[id] = 0;
}

void update(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        apply(id, r - l + 1);
        return;
    }
    down(id, l, r);
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v);
    update(id * 2 + 1, mid + 1, r, u, v);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return st[id];
    down(id, l, r);
    ll mid = (l + r) >> 1;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

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

    cin >> n >> m;
    while (m--) {
        ll t, s, e;
        cin >> t >> s >> e;
        if (t == 0) update(1, 1, n, s, e);
        else cout << get(1, 1, n, s, e) << '\n';
    }
}

Input6 7
1 1 6
0 2 5
1 1 3
0 3 6
1 2 6
0 1 6
1 1 6

Output0
2
2
4

Mỗi thao tác $O(\log N)$.

Thẻ là một hàm: gán, cộng, nhân

Khi có hai loại cập nhật đoạn trở lên, thứ tự bắt đầu quan trọng. “Cộng 5 rồi gán 2” cho mọi phần tử bằng 2; “gán 2 rồi cộng 5” cho 7. Thẻ của một nút phải nhớ đúng hiệu ứng gộp của cả chuỗi thao tác chưa đẩy xuống, theo đúng thứ tự thời gian.

Cách gọn nhất là coi thẻ là một hàm bậc nhất $f(x) = b \cdot x + c$ áp lên từng phần tử. Cộng $y$ là thẻ $(b, c) = (1, y)$; gán $y$ là $(0, y)$; nhân $y$ là $(y, 0)$; thẻ “không làm gì” là $(1, 0)$. Hai điều cần tính:

• Áp thẻ lên một nút dài $len$ với tổng $s$: tổng của $b x_i + c$ trên $len$ phần tử là $b \cdot s + c \cdot len$.
• Hợp thẻ. Thẻ $g = (b_g, c_g)$ chạy sau thẻ $f = (b_f, c_f)$ cho $g(f(x)) = b_g (b_f x + c_f) + c_g$, tức thẻ $(b_g b_f,\; b_g c_f + c_g)$.

Phép gán tự xóa mọi thứ trước nó: hợp $(0, y)$ sau bất kỳ $(b_f, c_f)$ cho $(0, y)$. Còn “cộng 5 rồi gán 2” là $(0, 2)$ và “gán 2 rồi cộng 5” là $(1, 5)$ hợp sau $(0, 2)$, cho $(0, 7)$, khớp với phép tính tay.

Thẻ ở cha luôn mới hơn thẻ ở con. Thẻ chỉ được đặt lên một nút khi thao tác đi tới nút đó, mà muốn tới nút đó thì mọi tổ tiên phải đã đẩy thẻ xuống và đang trống; vì vậy mọi thẻ được đặt sau này lên tổ tiên đều đến sau những thẻ đang nằm ở con. Do đó khi đẩy xuống, thẻ mới của con là thẻ cha hợp sau thẻ con.

Để cách làm này đúng, một loại thẻ cần ba điều kiện. Một, thẻ đóng kín với phép hợp và có thẻ “không làm gì”. Hai, áp thẻ lên một nút tính được chỉ từ tóm tắt của nút đó và độ dài đoạn. Ba, áp thẻ lên tóm tắt của đoạn ghép cho cùng kết quả với việc áp thẻ lên hai tóm tắt thành phần rồi ghép lại. Với tổng (và cả min), phép gán và phép cộng thỏa đủ ba điều kiện. Nhưng “cộng $c$ vào mọi phần tử” lên đoạn con có tổng lớn nhất thì không: số phần tử của đoạn tối ưu đổi theo $c$. Thao tác $a_i \gets \min(a_i, c)$ trên cả đoạn cũng vậy; loại này cần kỹ thuật riêng (bài 66). Nếu thẻ có phép nhân thì $b$ nhân dồn và dễ tràn; đề thường cho modulo, và ta lấy modulo mọi phép nhân, cộng.

Ví dụCộng, Gán Và Lấy Tổng

Đề. Mảng $N \le 2 \cdot 10^5$ số, $Q \le 2 \cdot 10^5$ thao tác trên đoạn $[L, R]$: 1 L R X cộng $X$; 2 L R X gán bằng $X$; 3 L R in tổng. $1 \le A_i, X \le 10^6$.

Lời giải. Thẻ là cặp (mul, add) như trên, nghĩa là “mỗi ô $x$ của đoạn thành $\mathrm{mul} \cdot x + \mathrm{add}$”, ban đầu $(1, 0)$. Cộng $X$ là thẻ $(1, X)$, gán $X$ là $(0, X)$. Không cần xét riêng “nút này đang có thẻ gán hay thẻ cộng”: mọi trường hợp đã nằm trong công thức hợp.

Bước 1: áp một thẻ $(b, c)$ lên nút. Tổng của đoạn dài $len$ thành $b \cdot \mathrm{st} + c \cdot len$. Thẻ mới đến sau thẻ cũ, nên ô $x$ đi qua cả hai thành $b(\mathrm{mul} \cdot x + \mathrm{add}) + c$: thẻ hợp là $(b \cdot \mathrm{mul},\ b \cdot \mathrm{add} + c)$.

void apply(ll id, ll len, ll b, ll c) {
    st[id] = b * st[id] + c * len;
    mul[id] = b * mul[id];
    ad[id] = b * ad[id] + c;
}

Bước 2: đẩy thẻ xuống. Thẻ trung hòa $(1, 0)$ thì bỏ qua; còn lại áp (mul, add) của cha lên hai con rồi đặt thẻ cha về $(1, 0)$. build phải khởi tạo mul = 1 cho mọi nút, vì mảng toàn cục bắt đầu bằng 0 và thẻ $(0, 0)$ nghĩa là “gán bằng 0”.

void down(ll id, ll l, ll r) {
    if (mul[id] == 1 && ad[id] == 0) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, mid - l + 1, mul[id], ad[id]);
    apply(id * 2 + 1, r - mid, mul[id], ad[id]);
    mul[id] = 1;
    ad[id] = 0;
}

Bước 3: hai loại sửa, một hàm. update nhận thẻ $(b, c)$ và theo đúng khung cây lười; ở main, cộng gọi với $(1, X)$, gán gọi với $(0, X)$.

if (t == 1) update(1, 1, n, l, r, 1, x);
else update(1, 1, n, l, r, 0, x);

Một phần tử có thể tới cỡ $2 \cdot 10^{11}$, tổng cả mảng tới $4 \cdot 10^{16}$, vẫn vừa ll. Với ví dụ, sau khi cộng 3 vào $[2, 4]$ rồi gán 2 cho $[3, 5]$, mảng là $(1, 5, 2, 2, 2)$, tổng 12.

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

const ll N = 2e5 + 5;
ll n, q, a[N], st[4 * N], mul[4 * N], ad[4 * N];

void build(ll id, ll l, ll r) {
    mul[id] = 1;
    if (l == r) {
        st[id] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

void apply(ll id, ll len, ll b, ll c) {
    st[id] = b * st[id] + c * len;
    mul[id] = b * mul[id];
    ad[id] = b * ad[id] + c;
}

void down(ll id, ll l, ll r) {
    if (mul[id] == 1 && ad[id] == 0) return;
    ll mid = (l + r) >> 1;
    apply(id * 2, mid - l + 1, mul[id], ad[id]);
    apply(id * 2 + 1, r - mid, mul[id], ad[id]);
    mul[id] = 1;
    ad[id] = 0;
}

void update(ll id, ll l, ll r, ll u, ll v, ll b, ll c) {
    if (v < l || r < u) return;
    if (u <= l && r <= v) {
        apply(id, r - l + 1, b, c);
        return;
    }
    down(id, l, r);
    ll mid = (l + r) >> 1;
    update(id * 2, l, mid, u, v, b, c);
    update(id * 2 + 1, mid + 1, r, u, v, b, c);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

ll get(ll id, ll l, ll r, ll u, ll v) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return st[id];
    down(id, l, r);
    ll mid = (l + r) >> 1;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

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

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        ll t, l, r;
        cin >> t >> l >> r;
        if (t == 3) {
            cout << get(1, 1, n, l, r) << '\n';
            continue;
        }
        ll x;
        cin >> x;
        if (t == 1) update(1, 1, n, l, r, 1, x);
        else update(1, 1, n, l, r, 0, x);
    }
}

Input5 7
1 2 3 4 5
3 1 5
1 2 4 3
3 2 5
2 3 5 2
3 1 5
1 1 3 4
3 2 4

Output15
23
12
17

Mỗi thao tác $O(\log N)$.

Cài đặt không đệ quy và các biến thể

Khi chỉ cần cập nhật điểm và truy vấn đoạn, có cách cài đặt ngắn hơn, chạy nhanh hơn và dùng $2n$ ô. Đặt lá của vị trí $i$ (đánh số từ 0) ở st[n + i]; khi đó cha của nút $v$ là $v/2$. Dựng cây là một vòng lặp lùi từ $n - 1$ về 1, cập nhật điểm là đi từ lá lên gốc. Với truy vấn trên đoạn nửa mở $[l, r)$, đi từ hai biên lên: nếu l lẻ, tức là con phải, thì cha của nó chứa phần tử bên trái l, nằm ngoài đoạn hỏi, nên phải lấy riêng st[l] rồi dịch l sang bên phải; nếu r lẻ thì lấy riêng st[r - 1]. Hai biên gặp nhau thì dừng.

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

const ll N = 1e5 + 5;
ll n, q, st[2 * N];

void update(ll pos, ll val) {
    for (st[pos += n] = val; pos > 1; pos >>= 1) st[pos >> 1] = min(st[pos], st[pos ^ 1]);
}

ll get(ll l, ll r) {
    ll res = 1e18;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res = min(res, st[l++]);
        if (r & 1) res = min(res, st[--r]);
    }
    return res;
}

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

    cin >> n >> q;
    for (ll i = 0; i < n; i++) cin >> st[n + i];
    for (ll i = n - 1; i >= 1; i--) st[i] = min(st[i * 2], st[i * 2 + 1]);
    while (q--) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) update(x, y);
        else cout << get(x, y) << '\n';
    }
}

Input6 6
4 9 2 7 5 6
2 0 6
2 1 4
1 2 8
2 1 4
2 3 6
1 0 1

Output2
2
7
5

Với phép gộp giao hoán (min, max, tổng, gcd) mã này đúng với mọi $n$, kể cả khi $n$ không phải lũy thừa của 2, như ví dụ có $n = 6$. Với phép không giao hoán ta đệm số lá lên lũy thừa của 2 bằng phần tử trung hòa rồi giữ hai biến tích lũy, một cho phía trái (nối thêm vào cuối) và một cho phía phải (nối thêm vào đầu), rồi gộp hai biến ở cuối. Bản không đệ quy có thẻ lười cũng tồn tại nhưng phức tạp hơn nhiều; khi cần thẻ lười, bản đệ quy dễ viết đúng hơn.

Vài biến thể thường gặp khác:

• Vị trí rất lớn. Nếu tọa độ tới $10^9$ nhưng chỉ có $q$ thao tác thì nén tọa độ (nếu biết trước tất cả thao tác), hoặc chỉ tạo nút khi cần, gọi là cây động: mỗi cập nhật tạo thêm không quá $\log_2 C + 1$ nút.
• Cây theo giá trị. Chỉ số của cây là giá trị, nút lưu số lần xuất hiện. Thêm, xóa, đếm số phần tử trong khoảng giá trị và tìm phần tử nhỏ thứ $k$ đều $O(\log C)$.
• Chọn công cụ. Dãy không đổi: tổng tiền tố cho tổng (bài 02), bảng thưa cho min/max (bài 22). Có sửa điểm và chỉ cần tổng hay đếm: cây Fenwick (bài 16) ngắn hơn. Còn lại, tức phép gộp không có phép ngược, tóm tắt nhiều thành phần, hoặc cập nhật đoạn: cây phân đoạn.

Ví dụPhép Gộp Xen Kẽ

Đề. Dãy đúng $2^n$ số ($n \le 17$). Rút gọn theo tầng: tầng đầu thay từng cặp kề bằng OR, tầng kế bằng XOR, rồi OR, XOR xen kẽ tới khi còn một số. Có $m \le 10^5$ lần gán một phần tử; sau mỗi lần in số cuối cùng.

Lời giải. Quá trình rút gọn chính là một cây phân đoạn đầy đủ với $2^n$ lá, chỉ khác phép gộp đổi theo tầng: nút cách lá $h$ tầng gộp bằng OR nếu $h$ lẻ, XOR nếu $h$ chẵn. Nút $v$ ở độ sâu $\lfloor \log_2 v \rfloor$ nên cách lá $h = n - \lfloor \log_2 v \rfloor$ tầng. Cài kiểu không đệ quy: lá $i$ ở st[2^n + i - 1], dựng lùi từ $2^n - 1$ về 1, mỗi lần gán đi từ lá lên gốc và gộp đúng phép của tầng. Đáp án là st[1]. Mỗi lần gán $O(n)$. Với ví dụ, $(4 \mid 6) \oplus (3 \mid 5) = 6 \oplus 7 = 1$.