Cây phân đoạn (Segment Tree)

Mức độ: Chuyên sâu

Cây Fenwick làm tốt tổng đoạn có cập nhật, nhưng không làm được nhỏ nhất trên đoạn khi dãy thay đổi, hay gán cả đoạn bằng một giá trị. Cây phân đoạn làm được gần như mọi câu hỏi trên đoạn, miễn là thông tin của một đoạn ghép được từ thông tin của hai nửa.

Cấu trúc cây

Nút gốc quản lý cả dãy [0, n - 1]. Mỗi nút quản lý đoạn [l, r] có hai con: con trái quản lý [l, giữa], con phải quản lý [giữa + 1, r]. Nút lá quản lý một phần tử. Mỗi nút giữ thông tin của đoạn mình quản lý, ví dụ số nhỏ nhất.

Dãy 5 2 4 7 1 3 (đoạn ghi theo vị trí, giá trị nhỏ nhất trong ngoặc):

                 [0,5] (1)
              /             \
      [0,2] (2)              [3,5] (1)
       /      \               /      \
  [0,1] (2)  [2] (4)     [3,4] (1)  [5] (3)
   /    \                 /    \
[0] (5) [1] (2)        [3] (7) [4] (1)

Cây có khoảng 2n nút, cao khoảng log₂n tầng. Lưu trong mảng: nút gốc là số 1, con của nút i là 2i và 2i + 1, mảng cần khoảng 4n ô.

Hỏi đoạn [x, y]: đi từ gốc. Đoạn của nút nằm hẳn trong [x, y] thì lấy luôn thông tin của nút; nằm hẳn ngoài thì bỏ qua; còn lại thì hỏi tiếp hai con rồi ghép. Mỗi tầng chỉ có nhiều nhất bốn nút được thăm, nên mỗi câu hỏi khoảng 4 × log₂n bước.

Sửa một phần tử: sửa lá, rồi đi ngược lên gốc, tính lại mỗi nút cha từ hai con. Khoảng log₂n bước.

Python

import sys
sys.setrecursionlimit(10000)

def xay(nut, l, r):
    if l == r:
        cay[nut] = a[l]
        return
    giua = (l + r) // 2
    xay(2 * nut, l, giua)
    xay(2 * nut + 1, giua + 1, r)
    cay[nut] = min(cay[2 * nut], cay[2 * nut + 1])

def sua(nut, l, r, vi_tri, gia_tri):
    if l == r:
        cay[nut] = gia_tri
        return
    giua = (l + r) // 2
    if vi_tri <= giua:
        sua(2 * nut, l, giua, vi_tri, gia_tri)
    else:
        sua(2 * nut + 1, giua + 1, r, vi_tri, gia_tri)
    cay[nut] = min(cay[2 * nut], cay[2 * nut + 1])

def hoi(nut, l, r, x, y):
    if y < l or r < x:                 # hẳn ngoài
        return float('inf')
    if x <= l and r <= y:              # hẳn trong
        return cay[nut]
    giua = (l + r) // 2
    return min(hoi(2 * nut, l, giua, x, y), hoi(2 * nut + 1, giua + 1, r, x, y))

du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
a = list(map(int, du_lieu[2:2 + n]))
cay = [0] * (4 * n)
xay(1, 0, n - 1)
ket_qua = []
vt = 2 + n
for _ in range(q):
    loai, x, y = du_lieu[vt], int(du_lieu[vt + 1]), int(du_lieu[vt + 2])
    vt += 3
    if loai == '1':
        sua(1, 0, n - 1, x - 1, y)                       # gán a[x] = y
    else:
        ket_qua.append(hoi(1, 0, n - 1, x - 1, y - 1))   # nhỏ nhất từ x đến y
print("\n".join(map(str, ket_qua)))

C++

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

int n;
vector<long long> a, cay;

void xay(int nut, int l, int r) {
    if (l == r) {
        cay[nut] = a[l];
        return;
    }
    int giua = (l + r) / 2;
    xay(2 * nut, l, giua);
    xay(2 * nut + 1, giua + 1, r);
    cay[nut] = min(cay[2 * nut], cay[2 * nut + 1]);
}

void sua(int nut, int l, int r, int viTri, long long giaTri) {
    if (l == r) {
        cay[nut] = giaTri;
        return;
    }
    int giua = (l + r) / 2;
    if (viTri <= giua) sua(2 * nut, l, giua, viTri, giaTri);
    else sua(2 * nut + 1, giua + 1, r, viTri, giaTri);
    cay[nut] = min(cay[2 * nut], cay[2 * nut + 1]);
}

long long hoi(int nut, int l, int r, int x, int y) {
    if (y < l || r < x) return LLONG_MAX;          // hẳn ngoài
    if (x <= l && r <= y) return cay[nut];         // hẳn trong
    int giua = (l + r) / 2;
    return min(hoi(2 * nut, l, giua, x, y), hoi(2 * nut + 1, giua + 1, r, x, y));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    a.resize(n);
    for (auto &x : a) cin >> x;
    cay.assign(4 * n, 0);
    xay(1, 0, n - 1);
    while (q--) {
        int loai, x;
        long long y;
        cin >> loai >> x >> y;
        if (loai == 1) sua(1, 0, n - 1, x - 1, y);                       // gán a[x] = y
        else cout << hoi(1, 0, n - 1, x - 1, y - 1) << "\n";             // nhỏ nhất từ x đến y
    }
    return 0;
}

Ghép thông tin của hai nửa

Đổi min thành phép khác là được cây cho bài khác. Điều kiện duy nhất: biết thông tin của hai nửa thì tính được thông tin của cả đoạn.

Thông tin của nút	Ghép từ con trái T và con phải P
tổng	T + P
nhỏ nhất, lớn nhất, ƯCLN	min, max, ƯCLN của T và P
lớn nhất và số lần xuất hiện	lấy bên lớn hơn; bằng nhau thì cộng số lần
đoạn con tổng lớn nhất	giữ bốn số: tổng, tiền tố lớn nhất, hậu tố lớn nhất, đoạn con lớn nhất; đoạn con tốt nhất của cả đoạn nằm hẳn bên trái, hẳn bên phải, hoặc vắt qua giữa (hậu tố của T + tiền tố của P)

Cập nhật lười

Cộng v vào cả đoạn [x, y]: nếu sửa từng phần tử thì mỗi lần mất tới n bước. Cập nhật lười (lazy propagation): khi một nút nằm hẳn trong [x, y], chỉ sửa thông tin của nút đó và ghi chú “cả đoạn này còn nợ cộng v” vào nút, không đi xuống các con. Khi nào cần đi xuống con (để hỏi hay sửa một phần), mới đẩy ghi chú xuống hai con.

Với tổng: nút quản lý đoạn dài len, cộng v vào cả đoạn thì tổng tăng v × len. Nhờ ghi chú, mỗi lần cộng đoạn chỉ thăm khoảng 4 × log₂n nút, giống một câu hỏi.

Python

def day_xuong(nut, l, r):
    if no[nut]:
        giua = (l + r) // 2
        for con, cl, cr in ((2 * nut, l, giua), (2 * nut + 1, giua + 1, r)):
            tong[con] += no[nut] * (cr - cl + 1)
            no[con] += no[nut]
        no[nut] = 0

def cong_doan(nut, l, r, x, y, v):
    if y < l or r < x:
        return
    if x <= l and r <= y:
        tong[nut] += v * (r - l + 1)
        no[nut] += v                  # ghi chú, chưa đi xuống
        return
    day_xuong(nut, l, r)
    giua = (l + r) // 2
    cong_doan(2 * nut, l, giua, x, y, v)
    cong_doan(2 * nut + 1, giua + 1, r, x, y, v)
    tong[nut] = tong[2 * nut] + tong[2 * nut + 1]

def tong_doan(nut, l, r, x, y):
    if y < l or r < x:
        return 0
    if x <= l and r <= y:
        return tong[nut]
    day_xuong(nut, l, r)
    giua = (l + r) // 2
    return tong_doan(2 * nut, l, giua, x, y) + tong_doan(2 * nut + 1, giua + 1, r, x, y)

C++

vector<long long> tong, no;

void dayXuong(int nut, int l, int r) {
    if (no[nut] == 0) return;
    int giua = (l + r) / 2;
    tong[2 * nut] += no[nut] * (giua - l + 1);
    no[2 * nut] += no[nut];
    tong[2 * nut + 1] += no[nut] * (r - giua);
    no[2 * nut + 1] += no[nut];
    no[nut] = 0;
}

void congDoan(int nut, int l, int r, int x, int y, long long v) {
    if (y < l || r < x) return;
    if (x <= l && r <= y) {
        tong[nut] += v * (r - l + 1);
        no[nut] += v;                 // ghi chú, chưa đi xuống
        return;
    }
    dayXuong(nut, l, r);
    int giua = (l + r) / 2;
    congDoan(2 * nut, l, giua, x, y, v);
    congDoan(2 * nut + 1, giua + 1, r, x, y, v);
    tong[nut] = tong[2 * nut] + tong[2 * nut + 1];
}

long long tongDoan(int nut, int l, int r, int x, int y) {
    if (y < l || r < x) return 0;
    if (x <= l && r <= y) return tong[nut];
    dayXuong(nut, l, r);
    int giua = (l + r) / 2;
    return tongDoan(2 * nut, l, giua, x, y) + tongDoan(2 * nut + 1, giua + 1, r, x, y);
}

Lưu ý: cây phân đoạn viết bằng Python chạy chậm hơn C++ nhiều lần (mỗi câu hỏi gọi đệ quy vài chục lần). Với n, q tới 2 × 10⁵, nên dùng C++ khi thi.

Luyện tập

Gồm 16 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 một phần tử, hỏi đoạn

Bài 1. Sửa phần tử, nhỏ nhất trên đ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 (gán a_i = v) hoặc 2 l r (hỏi số nhỏ nhất từ a_l đến a_r). In ra đáp số các câu hỏi loại 2.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

-8
-2
1
4

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

Bài 2. Sửa phần tử, ƯCLN trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹), q dòng sau mỗi dòng là 1 i v (gán a_i = v, 1 ≤ v ≤ 10⁹) hoặc 2 l r (hỏi ƯCLN của 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 12 18 24 9 6 2 1 3 1 4 36 2 1 5 2 4 4	6 6 36

Kiểm tra: nhập

6 5
100 75 50 30 45 60
2 1 3
2 4 6
1 3 7
2 1 3
2 2 6

Xem đáp số

25
15
1
1

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

Bài 3. Sửa 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 (gán a_i = v) 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 2 3 4 5 2 2 4 1 3 -7 2 1 5 2 3 3	9 5 -7

Kiểm tra: nhập

6 5
10 -10 20 -20 30 -30
2 1 6
1 1 0
2 1 3
1 6 100
2 4 6

Xem đáp số

0
10
110

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

Bài 4. Lớn nhất và vị trí

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 (gán a_i = v) hoặc 2 l r. Với câu hỏi loại 2, in ra số lớn nhất trong đoạn và vị trí của nó (đánh số từ 1; có nhiều vị trí thì in vị trí nhỏ nhất).

Ví dụ:

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

Kiểm tra: nhập

6 5
5 5 5 5 5 5
2 2 5
1 4 9
2 1 6
1 4 -1
2 3 6

Xem đáp số

5 2
9 4
5 3

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

Nhóm 2. Ghép thông tin phức tạp hơn

Bài 5. Lớn nhất và số lần xuất hiệ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 (gán a_i = v) hoặc 2 l r. Với câu hỏi loại 2, in ra số lớn nhất trong đoạn và số lần nó xuất hiện trong đoạn.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

3 5
3 1
9 1
2 2

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

Bài 6. Đoạn con tổng lớn nhất có cập nhật

Dòng đầu có n, q (1 ≤ n, q ≤ 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 (gán a_i = v) hoặc 2 l r. Với câu hỏi loại 2, in ra tổng lớn nhất của một đoạn con khác rỗng nằm trong [l, r].

Ví dụ:

Nhập	In ra
6 4 2 -5 3 -1 4 -2 2 1 6 2 1 2 1 2 5 2 1 6	6 2 13

Kiểm tra: nhập

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

Xem đáp số

-1
10
-1
-2

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

Bài 7. Dãy ngoặc đúng trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai là xâu n ký tự ( và ), q dòng sau mỗi dòng là 1 i (đổi ký tự thứ i sang ngoặc ngược lại) hoặc 2 l r. Với câu hỏi loại 2, in ra YES nếu đoạn ký tự từ l đến r là dãy ngoặc đúng, ngược lại NO.

Ví dụ:

Nhập	In ra
6 4 (()()) 2 1 6 2 2 5 1 3 2 1 6	YES YES NO

Kiểm tra: nhập

8 6
(())()()
2 1 4
2 2 3
1 4
2 1 4
1 1
2 1 2

Xem đáp số

YES
YES
NO
NO

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

Nhóm 3. Tìm vị trí trên cây

Bài 8. Vị trí đầu tiên không nhỏ hơn x

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 (gán a_i = v) hoặc 2 x (hỏi vị trí nhỏ nhất i có a_i ≥ x, hoặc -1 nếu không có). In ra đáp số các câu hỏi loại 2.

Ví dụ:

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

Kiểm tra: nhập

8 6
-3 -3 5 0 9 2 9 1
2 6
2 10
1 5 -1
2 6
1 1 6
2 6

Xem đáp số

5
-1
7
1

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

Bài 9. Số 1 thứ k

Dãy n bit (0 hoặc 1). Dòng đầu có n, q (1 ≤ n, q ≤ 2 × 10⁵), dòng thứ hai là xâu n ký tự 0/1, q dòng sau mỗi dòng là 1 i (đổi bit thứ i) hoặc 2 k (hỏi vị trí của bit 1 thứ k tính từ trái, hoặc -1 nếu có ít hơn k bit 1). In ra đáp số các câu hỏi loại 2.

Ví dụ:

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

Kiểm tra: nhập

10 6
0000000001
2 1
1 3
2 1
2 2
1 10
2 2

Xem đáp số

10
3
10
-1

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

Nhóm 4. Cập nhật lười

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

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 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 2 3 4 5 1 2 4 10 2 1 5 1 1 5 -1 2 3 3	45 12

Kiểm tra: nhập

6 6
0 0 0 0 0 0
1 1 6 3
1 2 3 -5
2 1 6
1 6 6 100
2 3 6
2 1 2

Xem đáp số

8
107
1

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

Bài 11. Cộng đoạn, nhỏ nhất trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 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 số nhỏ nhất từ a_l đến a_r). In ra đáp số các câu hỏi loại 2.

Ví dụ:

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

Kiểm tra: nhập

6 6
10 20 30 40 50 60
1 4 6 -35
2 1 6
1 1 1 100
2 1 3
1 1 6 1
2 4 4

Xem đáp số

5
20
6

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

Bài 12. Gán đoạn, tổng đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng là 1 l r v (gán mọi a_l, …, a_r bằng v, |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 2 3 4 5 1 2 4 0 2 1 5 1 3 5 7 2 2 4	6 14

Kiểm tra: nhập

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

Xem đáp số

12
44
20

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

Bài 13. Lật bit trên đoạn

Dãy n bit ban đầu toàn 0. Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), q dòng sau mỗi dòng là 1 l r (lật mọi bit từ l đến r: 0 thành 1, 1 thành 0) hoặc 2 l r (hỏi số bit 1 từ l đến r). In ra đáp số các câu hỏi loại 2.

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

6
1
1

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

Bài 14. Nhân và cộng trên đoạn

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

Ví dụ:

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

Kiểm tra: nhập

5 5
1 1 1 1 1
2 1 5 3
1 2 4 10
3 1 5
2 3 3 1000000006
3 2 4

Xem đáp số

128
119

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

Nhóm 5. Kỹ thuật khác

Bài 15. Lấy căn trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10¹²), q dòng sau mỗi dòng là 1 l r (thay mọi a_i với l ≤ i ≤ r bằng phần nguyên căn bậc hai của nó) 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 100 5 64 0 2 1 5 1 2 4 2 1 5 1 1 5	170 21

Kiểm tra: nhập

6 6
1000000000000 2 3 16 81 7
1 1 6
2 1 6
1 1 3
2 1 3
1 1 6
2 1 6

Xem đáp số

1000017
1002
39

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

Bài 16. Đếm số nhỏ hơn x trong đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|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 số phần tử a_i với l ≤ i ≤ r và a_i nhỏ hơn x. Phải trả lời theo đúng thứ tự (coi như không biết trước các câu hỏi).

Ví dụ:

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

Kiểm tra: nhập

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

Xem đáp số

3
3
2
0

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.