Segment Tree

IHỏi min đoạn trên dãy bị sửa

Bài toán: cho dãy $a_1, a_2, \dots, a_n$ và $q$ thao tác. Mỗi thao tác thuộc một trong hai loại: gán $a_k$ bằng một giá trị mới, hoặc hỏi số nhỏ nhất trong đoạn $[l, r]$. Từ đây ta viết tắt số nhỏ nhất là min.

Cách dễ nghĩ ra nhất là gán trực tiếp, còn mỗi câu hỏi thì duyệt cả đoạn:

if (t == 1) a[k] = x;
else {
    ll res = 1e18;
    for (ll i = l; i <= r; i++) res = min(res, a[i]);
    cout << res << '\n';
}

Độ phức tạp: gán $O(1)$, mỗi câu hỏi $O(n)$; với $n = q = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^{10}$ phép tính.

Tổng tiền tố (bài 0.3) không giúp được ở đây vì hai lý do: phép min không có phép ngược để gỡ phần đầu ra, và mỗi lần gán một phần tử làm sai mọi tiền tố đứng sau nó. Ta có thể thấy được điểm lãng phí của cách duyệt: các câu hỏi khác nhau thường chồng lên nhau, nhưng câu hỏi nào cũng duyệt lại từ đầu. Ta muốn tính sẵn min của một số đoạn, đủ ít để khi một phần tử đổi chỉ phải sửa vài đoạn, nhưng cũng đủ nhiều để ghép được thành mọi đoạn được hỏi.

Cách chọn các đoạn là chia đôi. Đoạn $[l, r]$ với $l < r$ được tách tại $mid = \lfloor \frac{l + r}{2} \rfloor$ thành hai nửa $[l, mid]$ và $[mid + 1, r]$; mỗi nửa lại được tách tiếp như vậy, cho tới khi đoạn chỉ còn một phần tử. Các đoạn này xếp thành một cây:

• mỗi đoạn là một nút của cây, và ta nói nút đó quản lý đoạn đó;
• nút quản lý cả dãy $[1, n]$ là gốc;
• hai nửa của một đoạn là hai nút con của nút quản lý đoạn đó, gọi là con trái và con phải;
• nút quản lý đúng một phần tử là lá.

Mỗi nút lưu min của đoạn nó quản lý. Cây như vậy được gọi là cây phân đoạn. Hình dưới là cây của dãy $5, 2, 7, 3, 8, 1, 6, 4$. Nút cam nằm trọn trong đoạn hỏi, nút xanh cắt ngang biên của đoạn hỏi, nút mờ nằm ngoài đoạn hỏi. Bạn có thể đổi đoạn hỏi, hoặc gán một phần tử rồi bấm chạy:

Hỏi min đ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$.

Gán một phần tử. Gán $a_6 = 9$ chỉ làm thay đổi các nút có đoạn chứa vị trí $6$. Đó là các nút trên đường đi từ lá $[6, 6]$ lên gốc: $[6, 6]$, $[5, 6]$, $[5, 8]$, $[1, 8]$. Ta tính lại các nút này từ dưới lên, mỗi nút bằng min của hai con; mọi nút khác giữ nguyên.

Để cài đặt, ta đánh số các nút: gốc là nút $1$, hai con của nút $i$ là nút $2i$ và nút $2i + 1$. Min của nút $i$ lưu ở ô thứ $i$ của một mảng. Chương trình gồm ba hàm; cả ba đều đi từ gốc xuống, và nhận vào số hiệu của nút cùng đoạn mà nút đó quản lý:

• Dựng cây: ở lá, min là chính phần tử đó; ở nút khác, dựng hai con trước rồi lấy min của hai con.
• Gán một phần tử: đi xuống đúng con chứa vị trí cần gán, gán ở lá, rồi trên đường quay lên tính lại min của mỗi nút từ hai con.
• Hỏi đoạn: có ba trường hợp. Nút nằm ngoài đoạn hỏi thì trả về một số rất lớn, $10^{18}$, để không ảnh hưởng tới phép min. Nút nằm trọn trong đoạn hỏi thì trả về min đã lưu và dừng. Còn lại thì hỏi cả hai con rồi lấy min.

Với $n = 2 \cdot 10^5$, cây chỉ có khoảng $19$ tầng, nên gán một phần tử chỉ ghé khoảng $19$ nút. Với câu hỏi, chỉ những nút cắt ngang biên của đoạn hỏi mới đi tiếp xuống con, mà mỗi tầng có không quá hai nút như vậy; vì thế một câu hỏi ghé không quá bốn nút mỗi tầng (xem ô Chứng minh).

Còn một chi tiết: mảng lưu cây cần bao nhiêu ô? Cây có đúng $2n - 1$ nút, nhưng số hiệu của các nút không liền nhau.

Vì vậy mảng $2n$ ô có thể không đủ chỗ. Mảng $4n$ ô thì luôn đủ (xem ô Chứng minh).

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

Đề. Cho dãy $n \le 2 \cdot 10^5$ số và $q \le 2 \cdot 10^5$ yêu cầu, mỗi yêu cầu có một trong hai dạng: 1 k u gán ô thứ $k$ bằng $u$; 2 l r in số nhỏ nhất trong các ô từ $l$ đến $r$.

Lời giải. Đây đúng là bài toán của mục này. Trong code, mảng st lưu min của các nút; ba hàm build, update, get lần lượt là dựng cây, gán một phần tử và hỏi đoạn; mỗi hàm nhận số hiệu nút id cùng đoạn $[l, r]$ mà nút đó quản lý. Với ví dụ của đề, cả dãy $7, 2, 9, 2, 6$ có min là $2$; sau khi gán $a_2 = 8$, đoạn $[1, 3]$ có min là $7$.

#include <bits/stdc++.h>
using namespace std;
#define 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';
    }
}

ChạyInput5 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

Độ phức tạp: dựng cây $O(n)$, mỗi yêu cầu $O(\log n)$; với $n = q = 2 \cdot 10^5$ cần khoảng $1{,}5 \cdot 10^7$ lần ghé nút.

IILưu thông tin khác ở mỗi nút

Nhìn lại chương trình ở trên: phép min chỉ xuất hiện ở ba chỗ, là cách tính một nút từ hai con, giá trị của lá, và giá trị $10^{18}$ trả về cho nút nằm ngoài đoạn hỏi. Mọi phần còn lại chỉ nói về hình dạng của cây. Thay phép min bằng phép cộng và thay $10^{18}$ bằng $0$, ta có cây cho tổng đoạn; thay bằng phép lấy ước chung lớn nhất và $0$, ta 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 điều kiện.

Tổng quát, mỗi nút lưu một thông tin về đoạn nó quản lý, và cần có hai điều:

• Thông tin của một đoạn tính được từ thông tin của hai nửa, bằng một hàm mà ta gọi là phép gộp.
• Có một giá trị dành cho “đoạn rỗng”, gộp với nó thì không thay đổi gì, gọi là phần tử trung hòa. Hàm hỏi đoạn trả về phần tử trung hòa cho nút nằm ngoài đoạn hỏi.

Khi có đủ hai điều này, ba hàm của cây giữ nguyên, chỉ cần thay phép min bằng phép gộp.

Không phải thông tin nào cũng gộp được. Điều kiện thứ nhất đòi thông tin của nút cha phải tính được chỉ từ thông tin đã lưu ở hai nút con. Khi một đại lượng không gộp được một mình, cách thường dùng là lưu kèm vài đại lượng phụ, như ví dụ cuối mục này.

Cần chú ý thêm về thứ tự: phép gộp không nhất thiết phải giao hoán, tức là gộp nửa trái với nửa phải có thể cho kết quả khác gộp nửa phải với nửa trái. Vì vậy ta luôn gộp theo đúng thứ tự vị trí: nửa trái trước, nửa phải sau. Với min, tổng hay ước chung lớn nhất, thứ tự không ảnh hưởng; nhưng với ví dụ ngay dưới đây, đảo thứ tự sẽ cho kết quả sai.

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

Đề. Cho dãy $n \le 2 \cdot 10^5$ số với $|a_i| \le 10^9$, và $m \le 2 \cdot 10^5$ lần gán $a_k = 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, có tổng $0$.

Lời giải. Nếu mỗi nút chỉ lưu tổng lớn nhất của một đoạn con, ta chưa gộp được: đoạn con tốt nhất của đoạn ghép có thể vắt qua chỗ nối hai nửa, và khi đó nó gồm một đoạn ở cuối nửa trái nối với một đoạn ở đầu nửa phải. Vì vậy mỗi nút lưu bốn số:

• $\mathrm{sum}$: tổng cả đoạn;
• $\mathrm{pre}$: tổng lớn nhất của một đoạn ở đầu (tiền tố), được chọn đoạn rỗng;
• $\mathrm{suf}$: tổng lớn nhất của một đoạn ở cuối (hậu tố), được chọn đoạn rỗng;
• $\mathrm{best}$: tổng lớn nhất của một đoạn con, được chọn đoạn rỗng.

Gộp nửa trái $A$ với nửa phải $B$:

Lá có giá trị $x$ thì có tổng $x$, còn ba số kia bằng $\max(0, x)$: hoặc lấy chính phần tử đó, hoặc lấy đoạn rỗng. Bài chỉ hỏi cả dãy, nên sau mỗi lần gán, đáp án là $\mathrm{best}$ của gốc, không cần hàm hỏi đoạn.

Trong hình, mỗi nút giữ bốn số; bạn có thể đổi hai nửa để xem cách gộp:

Phép gộp này không giao hoán: gộp $2, -1$ với $4, -5$ theo đúng thứ tự cho $\mathrm{best} = 5$ (đoạn $2, -1, 4$), còn đổi chỗ thì ra $4$. Tổng có thể tới $2 \cdot 10^{14}$, nên các số dùng kiểu long long.

#include <bits/stdc++.h>
using namespace std;
#define 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';
    }
}

ChạyInput5 4
-3 2 -1 4 -5
1 -2
5 3
2 -6
4 -8

Output5
8
7
3

Độ phức tạp: dựng cây $O(n)$, mỗi lần gán $O(\log n)$; với $n = m = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^6$ lần gộp nút.

IIITìm vị trí bằng cách đi xuống cây

Có những bài không hỏi giá trị trên một đoạn mà hỏi một vị trí. Bài toán: cho dãy bit $b_1, b_2, \dots, b_n$, mỗi $b_i$ là $0$ hoặc $1$, và các thao tác xen kẽ nhau: đảo một bit, hoặc hỏi bit $1$ thứ $k$ tính từ trái nằm ở vị trí nào.

Ta có thể dùng cây lưu tổng, tức là số bit $1$ của mỗi đoạn, rồi chặt nhị phân (bài 0.6) trên vị trí: tìm vị trí $p$ nhỏ nhất mà đoạn $[1, p]$ có ít nhất $k$ bit $1$. Mỗi bước chặt cần một câu hỏi tốn $O(\log n)$, nên một lần tìm tốn $O(\log^2 n)$. Cây phân đoạn cho phép làm nhanh hơn, bằng cách đi thẳng từ gốc xuống một lá.

Mỗi nút lưu số bit $1$ trong đoạn của nó. Ta đi từ gốc xuống và luôn giữ điều sau: đáp án là bit $1$ thứ $k$ nằm trong đoạn của nút đang đứng. Tại một nút, nếu con trái có ít nhất $k$ bit $1$ thì đáp án nằm trong con trái; ta đi sang trái và giữ nguyên $k$. Ngược lại, đáp án nằm trong con phải; ta bỏ qua mọi bit $1$ của con trái, nên trừ số bit $1$ của con trái khỏi $k$ rồi đi sang phải. Mỗi bước xuống một tầng, và lá cuối cùng chính là đáp án. Trước khi đi, cần kiểm tra gốc có ít nhất $k$ bit $1$; nếu không thì không có đáp án.

Trong hình, mỗi nút ghi số bit $1$ trong đoạn của nó; đường cam là đường đi xuống:

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]);
}

Độ phức tạp: $O(\log n)$, với $n = 2 \cdot 10^5$ cần khoảng $19$ bước.

Lỗi hay gặp là quên trừ số bit $1$ của con trái khi đi sang phải: khi đó $k$ vẫn tính cả những bit $1$ đã bỏ qua, và đường đi lạc sang nhánh sai.

Cùng cách đi xuống đó dùng được cho câu hỏi “vị trí đầu tiên có $a_i \ge x$” trên cây lưu max: nếu max của con trái ít nhất $x$ thì đi sang trái, ngược lại đi sang phải. Ví dụ dưới đây làm đúng như vậy.

Sử dụng kiến thức này cũng có thể giải bài: tìm phần tử nhỏ thứ $k$ của một tập số đang được thêm và xóa. Cho chỉ số của cây là giá trị, mỗi lá đếm số lần giá trị đó có trong tập; phần tử nhỏ thứ $k$ chính là vị trí của “bit $1$ thứ $k$” theo cách đi xuống ở trên.

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

Đề. Có $n \le 2 \cdot 10^5$ khách sạn, khách sạn thứ $i$ còn $h_i$ phòng trống. Lần lượt $m \le 2 \cdot 10^5$ đoàn khách đến, đoàn thứ $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 trống; khách sạn đó bớt đi $r_j$ phòng. Nếu không có khách sạn nào đủ chỗ, in $0$.

Lời giải. Cây lưu max số phòng trống của mỗi đoạn khách sạn. Nếu max ở gốc nhỏ hơn $r_j$, không khách sạn nào đủ chỗ, ta in $0$. Ngược lại, ta đ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 là max của con trái ít nhất $r_j$. Tới lá là đúng khách sạn cần tìm. Hàm walk trong code vừa tìm vừa sửa trong một lượt: tới lá thì trừ đi $r_j$ phòng, và trên đường quay lên tính lại max của mỗi nút. Với ví dụ của đề, đoàn thứ hai cần $3$ phòng được xếp vào khách sạn $3$, vì lúc đó khách sạn $1$ chỉ còn $1$ phòng.

#include <bits/stdc++.h>
using namespace std;
#define 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';
}

ChạyInput4 5
3 1 4 2
2 3 1 4 2

Output1 3 1 0 4

Độ phức tạp: dựng cây $O(n)$, mỗi đoàn đi một đường từ gốc xuống lá tốn $O(\log n)$; với $n = m = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^6$ lần ghé nút.

IVCộng cả đoạn: thẻ lười

Bài toán: cho dãy $a_1, a_2, \dots, a_n$ và các thao tác xen kẽ nhau: cộng $x$ vào mọi phần tử của đoạn $[l, r]$, hoặc hỏi tổng của đoạn $[l, r]$.

Nếu cộng $x$ bằng cách gán lại từng vị trí trong đoạn, một thao tác có thể tốn $O(n \log n)$. Ta có thể thấy được điểm lãng phí: câu hỏi tổng đoạn chỉ đọc các nút lớn nhất nằm trọn trong đoạn hỏi, chứ không cần biết từng lá. Vì vậy thao tác cộng cũng chỉ nên sửa đúng những nút nằm trọn trong đoạn cần cộng, giống cách câu hỏi tìm các nút đó.

Với một nút nằm trọn trong đoạn cần cộng, tổng mới của nút tính được ngay: tổng cũ cộng $x$ nhân với độ dài đoạn. Còn các nút bên dưới thì ta chưa sửa vội, mà chỉ ghi lại ở nút đó: “mọi phần tử trong đoạn này cần cộng thêm $x$, nhưng hai nút con chưa được cộng”. Ghi chú này được gọi là thẻ lười (lazy tag). Chỉ khi một thao tác sau cần đi xuống các con của nút này, ta mới đẩy thẻ xuống: sửa tổng của hai con, chuyển thẻ thành thẻ của hai con, rồi xóa thẻ ở nút. Kỹ thuật này được gọi là cập nhật lười (lazy propagation).

Hai quy tắc dưới đây dùng cho cả thao tác cộng lẫn câu hỏi:

• Gặp nút nằm trọn trong đoạn: với thao tác cộng, sửa tổng của nút và cộng $x$ vào thẻ của nút; rồi dừng.
• Gặp nút cắt ngang biên: đẩy thẻ của nút xuống hai con trước khi đi xuống. Với thao tác cộng, khi quay lên thì tính lại tổng của nút từ hai con.

Trong hình, nhãn $+k$ màu xanh lá là thẻ chưa được đẩy xuống. Bạn có thể cộng thêm vào một đoạn, hoặc hỏi tổng một đoạn nhỏ để xem thẻ được đẩy:

Ta chạy tay trên dãy $5, 2, 7, 3, 8, 1, 6, 4$ với thao tác cộng $3$ vào đoạn $[2, 7]$. Hai nút $[3, 4]$ và $[5, 6]$ nằm trọn trong đoạn nên nhận thẻ $+3$, tổng thành $16$ và $15$. Hai lá $[2, 2]$ và $[7, 7]$ cũng nằm trọn trong đoạn, giá trị thành $5$ và $9$. Các nút cắt ngang biên được tính lại từ hai con, và gốc thành $54 = 36 + 6 \cdot 3$. Bốn lá từ $[3, 3]$ tới $[6, 6]$ chưa hề bị sửa. Nếu sau đó hỏi tổng đoạn $[3, 3]$, nút $[3, 4]$ cắt ngang biên nên thẻ $+3$ được đẩy xuống, và lá $[3, 3]$ trả về $7 + 3 = 10$.

Trong code, mảng st lưu tổng của các nút, mảng lz lưu thẻ. Hàm apply đặt thẻ $x$ lên một nút có độ dài $len$: tổng tăng $x \cdot len$, thẻ tăng $x$. Hàm down đẩy thẻ của một nút xuống hai con rồi xóa thẻ đó.

#include <bits/stdc++.h>
using namespace std;
#define 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';
    }
}

ChạyInput8 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

Độ phức tạp: dựng cây $O(n)$, mỗi thao tác $O(\log n)$; với $n = q = 2 \cdot 10^5$ cần khoảng $1{,}5 \cdot 10^7$ lần ghé nút.

#include <bits/stdc++.h>
using namespace std;
#define 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];
    ll mid = (l + r) >> 1;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

signed main() {
    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';
    }
}

ChạyInput3 2
1 2 3
1 1 2 5
2 1 1

Output1

VCộng và gán cùng lúc: hợp thẻ

Khi có từ hai loại cập nhật đoạn trở lên, thứ tự của chúng bắt đầu quan trọng. “Cộng $5$ rồi gán $2$” cho mọi phần tử bằng $2$, còn “gán $2$ rồi cộng $5$” cho mọi phần tử bằng $7$. Thẻ của một nút phải nhớ đúng tác dụng của cả chuỗi thao tác chưa được đẩ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 x + c$, áp lên từng phần tử của đoạn. Cộng $y$ là thẻ $(b, c) = (1, y)$; gán $y$ là thẻ $(0, y)$; nhân $y$ là thẻ $(y, 0)$; thẻ “không làm gì” là $(1, 0)$. Ta cần hai phép tính:

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

Kiểm tra lại với ví dụ trên: “cộng $5$ rồi gán $2$” là thẻ $(0, 2)$ hợp sau thẻ $(1, 5)$, cho $(0 \cdot 1,\ 0 \cdot 5 + 2) = (0, 2)$; “gán $2$ rồi cộng $5$” là thẻ $(1, 5)$ hợp sau thẻ $(0, 2)$, cho $(1 \cdot 0,\ 1 \cdot 2 + 5) = (0, 7)$. Cả hai đều khớp với phép tính tay.

Khi đẩy thẻ từ cha xuống con, thẻ của cha luôn đến sau thẻ đang có ở con (xem ô Chứng minh), nên thẻ mới của con là thẻ của cha hợp sau thẻ của con.

Cần cẩn thận: không phải loại thẻ nào cũng dùng được với mọi thông tin lưu ở nút. Thẻ phải áp được lên một nút chỉ từ thông tin đã lưu ở nút đó và độ dài đoạn. Chẳng hạn, cộng $c$ vào mọi phần tử thì tổng mới tính được ngay; nhưng tổng lớn nhất của một đoạn con thì không, vì đoạn con tốt nhất có thể thay đổi tùy theo $c$.

Sử dụng kiến thức này cũng có thể giải bài: nhân cả đoạn với một số, cộng một số vào cả đoạn, và hỏi tổng đoạn theo modulo. Thẻ vẫn là cặp $(b, c)$ như trên; chỉ cần lấy modulo sau mọi phép nhân và phép cộng.

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

Đề. Cho mảng $N \le 2 \cdot 10^5$ số và $Q \le 2 \cdot 10^5$ thao tác trên đoạn $[L, R]$: 1 L R X cộng $X$ vào mọi phần tử; 2 L R X gán mọi phần tử bằng $X$; 3 L R in tổng. Mọi $A_i$ và $X$ nằm trong khoảng từ $1$ tới $10^6$.

Lời giải. Thẻ là cặp $(b, c)$ như trên, nghĩa là “mỗi phần tử $x$ của đoạn thành $b x + c$”, ban đầu là $(1, 0)$. Cộng $X$ là thẻ $(1, X)$, gán $X$ là thẻ $(0, X)$. Ta không cần xét riêng nút đang có thẻ gán hay thẻ cộng, vì mọi trường hợp đã nằm trong công thức hợp thẻ. Trong code, hai mảng mul và ad lưu hai thành phần $b$ và $c$ của thẻ. Cần chú ý: hàm dựng cây phải đặt mul bằng $1$ cho mọi nút, vì mảng toàn cục ban đầu toàn số $0$, mà thẻ $(0, 0)$ lại có nghĩa là “gán bằng $0$”.

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

#include <bits/stdc++.h>
using namespace std;
#define 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);
    }
}

ChạyInput5 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

Độ phức tạp: dựng cây $O(N)$, mỗi thao tác $O(\log N)$; với $N = Q = 2 \cdot 10^5$ cần khoảng $1{,}5 \cdot 10^7$ lần ghé nút.

VICài đặt không đệ quy, nhanh hơn

Khi chỉ cần gán một phần tử và hỏi đoạn, không cần thẻ lười, ta có một cách cài đặt ngắn hơn, chạy nhanh hơn và chỉ dùng $2n$ ô. Cách này đánh số vị trí từ $0$ và dùng đoạn nửa mở $[l, r)$, tức là đoạn gồm các vị trí $l, l + 1, \dots, r - 1$.

Lá của vị trí $i$ đặt ở ô $n + i$, và cha của nút $v$ là nút $\lfloor v / 2 \rfloor$. Dựng cây là một vòng lặp lùi từ $n - 1$ về $1$; gán một phần tử là đi từ lá lên gốc, tính lại từng nút trên đường. Để hỏi đoạn $[l, r)$, ta đưa hai biên lên dần từng tầng:

• nếu $l$ là số lẻ thì nút $l$ là con phải, và cha của nó chứa cả nút nằm bên trái $l$, ngoài đoạn hỏi; vì vậy ta lấy riêng nút $l$ rồi dịch $l$ sang phải một ô;
• nếu $r$ là số lẻ thì nút $r - 1$ là con trái, và cha của nó chứa cả nút $r$, ngoài đoạn hỏi; vì vậy ta lấy riêng nút $r - 1$.

Sau đó cả hai biên cùng lên tầng trên, và ta dừng khi hai biên gặp nhau.

#include <bits/stdc++.h>
using namespace std;
#define 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';
    }
}

ChạyInput6 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

Độ phức tạp: dựng cây $O(n)$, mỗi thao tác $O(\log n)$; với $n = q = 10^5$ cần khoảng $3 \cdot 10^6$ phép tính.

Chương trình 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$, miễn là phép gộp giao hoán (min, max, tổng, ước chung lớn nhất). Với phép gộp không giao hoán, cần đệm số lá lên một lũy thừa của $2$ bằng phần tử trung hòa, rồi gộp riêng phần bên trái, phần bên phải và ghép hai phần lại ở cuối.

So với bản đệ quy, bản không đệ quy chạy nhanh hơn rõ rệt:

Bản không đệ quy nhanh hơn bản đệ quy khoảng $3{,}8$ lần, vì không tốn lời gọi hàm và mảng chỉ bằng một nửa. Vì vậy khi không cần thẻ lười và giới hạn thời gian chặt, nên cân nhắc dùng bản không đệ quy.