Segment Tree là một trong những cấu trúc dữ liệu quan trọng nhất khi bước từ các bài truy vấn mảng cơ bản sang những bài lập trình thi đấu thực sự đòi hỏi thiết kế trạng thái. Điều đáng học ở Segment Tree không nằm ở việc ghi nhớ một template cố định, mà ở khả năng nhìn một đoạn dữ liệu và xác định được Node cần lưu gì, hai đoạn phải gộp ra sao, cập nhật tác động thế nào và thông tin nào đủ mạnh để loại bỏ cả một nhánh của cây. Từ nền tảng range query và point update, tư duy này phát triển tự nhiên tới custom Node, tìm vị trí trực tiếp bằng tree walking, lazy propagation, hợp thành các phép biến đổi, Segment Tree Beats, Merge Sort Tree, Persistent Segment Tree, Euler Tour, Heavy-Light Decomposition, cây trên miền tọa độ lớn, Segment Tree trên trục thời gian và các bài kết hợp với DP, đồ thị hay sweep line. Khi học đến cuối lộ trình, mục tiêu không còn là “biết dùng Segment Tree”, mà là nhận ra chính xác lúc nào nó là cấu trúc phù hợp, lúc nào Fenwick Tree, prefix sum, Sparse Table hay một kỹ thuật khác đơn giản hơn, từ đó hình thành phản xạ lựa chọn và thiết kế cấu trúc dữ liệu thay vì chỉ áp dụng công thức có sẵn.

Đăng nhập để tham gia lộ trình luyện tập

SEGMENT TREE

Segment Tree là cấu trúc dữ liệu dùng để lưu thông tin của nhiều đoạn con của một mảng, nhờ đó có thể vừa cập nhật dữ liệu vừa trả lời truy vấn trên đoạn nhanh. Mỗi đỉnh của cây đại diện cho một đoạn $[l,r]$ , hai con lần lượt quản lý nửa trái và nửa phải. Thông tin của đỉnh cha được tạo bằng cách gộp thông tin hai đỉnh con.

Ý tưởng quan trọng nhất không phải là thuộc một đoạn code cố định, mà là trả lời được bốn câu hỏi: mỗi Node phải lưu gì, hai Node được merge như thế nào, phần tử trung hòa (identity) là gì, và phép cập nhật tác động lên Node ra sao. Khi có cập nhật đoạn, cần thêm ba câu hỏi nữa: tag lazy biểu diễn gì, apply một tag lên Node thế nào, và hai tag được compose theo thứ tự nào.

Với Segment Tree cơ bản trên mảng $n$ phần tử:

\text{build}=O(n)

\text{point update}=O(\log n)

\text{range query}=O(\log n)

Bản cài đặt đệ quy thường cấp phát khoảng $4n$ Node. Đây chỉ là cận thực hành thuận tiện; bản iterative Segment Tree có cách bố trí bộ nhớ khác.

Giai đoạn 1 - Nền tảng: xây cây, truy vấn và cập nhật điểm

Mỗi đỉnh quản lý một đoạn $[l,r]$ . Nếu $l=r$ , đỉnh là lá và tương ứng với đúng một phần tử của mảng. Nếu $l<r$ , đặt

mid=\left\lfloor\frac{l+r}{2}\right\rfloor.

Con trái quản lý $[l,mid]$ , con phải quản lý $[mid+1,r]$ .

Giả sử cần truy vấn tổng. Với hai đoạn con có tổng lần lượt là $L$ và $R$ , phép gộp là

merge(L,R)=L+R.

Phần tử trung hòa là $0$ vì

x+0=0+x=x.

Nếu chuyển sang truy vấn nhỏ nhất, phép gộp trở thành min và identity thường là $+\infty$ . Với truy vấn lớn nhất, identity thường là $-\infty$ . Chọn identity sai là một trong những lỗi phổ biến nhất khi viết hàm truy vấn tổng quát.

Mã giả xây cây:

build(node, l, r):
    nếu l = r:
        tree[node] = giá trị tại vị trí l
        kết thúc

    mid = (l + r) / 2
    build(con trái, l, mid)
    build(con phải, mid + 1, r)

    tree[node] = merge(tree[con trái], tree[con phải])

Khi truy vấn đoạn $[L,R]$ , có ba trường hợp.

Đỉnh hiện tại nằm hoàn toàn ngoài $[L,R]$ : trả identity.
Đỉnh hiện tại nằm hoàn toàn trong $[L,R]$ : trả luôn thông tin đã lưu.
Hai đoạn giao nhau một phần: truy vấn hai con rồi merge kết quả.

query(node, l, r, L, R):
    nếu [l, r] không giao [L, R]:
        trả identity

    nếu [l, r] nằm hoàn toàn trong [L, R]:
        trả tree[node]

    mid = (l + r) / 2
    trai = query(con trái, l, mid, L, R)
    phai = query(con phải, mid + 1, r, L, R)

    trả merge(trai, phai)

Cập nhật điểm chỉ làm thay đổi một lá và các đỉnh trên đường từ lá đó về gốc.

update(node, l, r, pos, value):
    nếu l = r:
        tree[node] = value
        kết thúc

    mid = (l + r) / 2

    nếu pos <= mid:
        update(con trái, l, mid, pos, value)
    ngược lại:
        update(con phải, mid + 1, r, pos, value)

    tree[node] = merge(tree[con trái], tree[con phải])

Một phép gộp dùng được trong Segment Tree phải có tính kết hợp:

(a\circ b)\circ c=a\circ(b\circ c).

Ta không cần phép gộp có tính giao hoán. Đây là điểm rất quan trọng vì ở các giai đoạn sau, thứ tự trái rồi phải có thể quyết định đáp án.

Giai đoạn 2 - Thiết kế Node, monoid và thứ tự trái-phải

Segment Tree mạnh nhất khi Node không còn là một số đơn lẻ. Ta có thể xem thông tin mỗi đoạn như một phần tử của một monoid: có phép gộp kết hợp và có identity. Tư duy thực chiến là thiết kế trạng thái nhỏ nhất nhưng đủ để hai đoạn kề nhau có thể ghép thành đoạn lớn hơn.

Node giữ nhiều cực trị

Nếu cần hai giá trị lớn nhất trên đoạn, Node có thể giữ max1 và max2. Khi gộp hai con, chỉ cần lấy hai phần tử lớn nhất trong bốn ứng viên từ hai Node con. Không cần lưu toàn bộ đoạn.

Node cho dãy ngoặc

Với mỗi đoạn, có thể lưu:

open: số ngoặc mở còn dư;
close: số ngoặc đóng còn dư;
match: số cặp ngoặc đã ghép được.

Khi ghép trái với phải, số cặp mới qua biên là

new=\min(L.open,R.close).

Sau đó:

open=L.open+R.open-new,

close=L.close+R.close-new,

match=L.match+R.match+new.

Thứ tự merge(L,R) không thể đảo tùy ý vì ngoặc mở ở bên trái mới có thể ghép với ngoặc đóng ở bên phải.

Node cho tổng con lớn nhất

Một Node kinh điển gồm bốn trường:

sum: tổng toàn đoạn;
pref: tổng tiền tố tốt nhất;
suff: tổng hậu tố tốt nhất;
best: tổng đoạn con liên tiếp tốt nhất.

Với hai con $L$ và $R$ :

sum=L.sum+R.sum,

pref=\max(L.pref,L.sum+R.pref),

suff=\max(R.suff,R.sum+L.suff),

best=\max(L.best,R.best,L.suff+R.pref).

Công thức cuối biểu diễn đúng ba khả năng: đáp án nằm hoàn toàn bên trái, hoàn toàn bên phải, hoặc đi qua biên giữa.

merge(L, R):
    C.sum = L.sum + R.sum
    C.pref = max(L.pref, L.sum + R.pref)
    C.suff = max(R.suff, R.sum + L.suff)
    C.best = max(L.best, R.best, L.suff + R.pref)
    trả C

Cần xác định rõ bài toán cho phép đoạn rỗng hay bắt buộc đoạn không rỗng. Hai quy ước này dẫn tới cách khởi tạo lá và identity khác nhau.

Node chỉ lưu đúng thứ cần thiết

Nếu câu hỏi chỉ cần tổng đoạn và tiền tố lớn nhất, không cần mang theo cả suff và best. Thiết kế Node tốt nghĩa là mỗi trường đều có lý do tồn tại và trực tiếp tham gia vào truy vấn hoặc merge.

Hàm hợp thành và phép gộp không giao hoán

Nếu mỗi phần tử là một hàm

f(x)=ax+b,

và một đoạn biểu diễn phép hợp các hàm theo thứ tự, thì đổi merge(L,R) thành merge(R,L) sẽ tạo ra hàm khác. Khi phép gộp không giao hoán, phải giữ đúng thứ tự trái-phải ở cả hàm truy vấn lẫn HLD sau này.

Một nguyên tắc hữu ích là: trước khi code Segment Tree, hãy thử tự viết hàm merge độc lập và kiểm tra bằng tay trên hai đoạn nhỏ. Nếu chưa giải thích được vì sao merge đúng, chưa nên viết phần cây.

Giai đoạn 3 - Đi xuống cây: first, last, k-th và block liên tiếp

Segment Tree không chỉ trả về một giá trị tổng hợp. Nếu Node cho phép biết chắc một nhánh có chứa đáp án hay không, ta có thể đi trực tiếp xuống cây để tìm vị trí.

Tìm phần tử thứ k theo tần suất

Giả sử lá lưu $1$ nếu phần tử còn tồn tại và $0$ nếu đã bị xóa. Mỗi Node lưu tổng số phần tử còn sống trong đoạn.

Tại một đỉnh, gọi leftCount là số phần tử còn sống ở con trái.

Nếu $k\le leftCount$ , đáp án ở con trái.
Nếu $k>leftCount$ , đáp án ở con phải với thứ hạng mới $k-leftCount$ .

find_kth(node, l, r, k):
    nếu l = r:
        trả l

    nếu tree[con trái].count >= k:
        đi xuống con trái với cùng k
    ngược lại:
        đi xuống con phải với k - tree[con trái].count

Nếu mỗi bước chỉ chọn đúng một con, độ phức tạp là

O(\log n).

Tìm vị trí đầu tiên thỏa điều kiện

Giả sử Node lưu giá trị lớn nhất. Muốn tìm vị trí đầu tiên từ mốc $L$ có giá trị ít nhất $x$ , ta có thể loại cả một node nếu:

đoạn của node nằm hoàn toàn trước $L$ ;
hoặc max < x.

Nếu node còn khả năng chứa đáp án, ưu tiên đi con trái trước để lấy vị trí nhỏ nhất.

find_first(node, l, r, L, x):
    nếu r < L:
        trả KHONG_CO

    nếu tree[node].max < x:
        trả KHONG_CO

    nếu l = r:
        trả l

    thử tìm ở con trái
    nếu tìm thấy:
        trả kết quả đó

    trả kết quả tìm ở con phải

Điều kiện cắt nhánh phải được suy ra từ thông tin thật sự lưu trong Node. Nếu điều kiện không đủ mạnh để loại nhánh, thuật toán có thể thoái hóa thành duyệt rất nhiều đỉnh.

Đoạn liên tiếp dài nhất

Với bài toán trạng thái nhị phân như ô trống/đã dùng, Node thường lưu:

len: độ dài đoạn;
pref: số vị trí hợp lệ liên tiếp từ đầu đoạn;
suff: số vị trí hợp lệ liên tiếp từ cuối đoạn;
best: độ dài block hợp lệ lớn nhất trong đoạn.

Khi gộp:

best=\max(L.best,R.best,L.suff+R.pref).

pref kéo dài qua biên chỉ khi toàn bộ đoạn trái hợp lệ. suff kéo dài qua biên chỉ khi toàn bộ đoạn phải hợp lệ.

Khi cần tìm block đầu tiên có độ dài ít nhất $k$ , thứ tự xét thường là:

nếu con trái có best >= k, đi trái;
nếu $L.suff+R.pref\ge k$ , đáp án cắt qua biên;
nếu không, đi phải.

Đây là một mẫu rất quan trọng: Node vừa dùng để trả lời truy vấn, vừa dùng như điều kiện điều hướng việc đi xuống cây.

Giai đoạn 4 - Lazy cơ bản: cộng, gán, đảo và hợp thành tag

Khi một cập nhật tác động lên cả đoạn, sửa từng lá sẽ mất $O(n)$ . Lazy propagation trì hoãn việc đẩy cập nhật xuống con. Mỗi node giữ hai loại thông tin: dữ liệu tổng hợp của đoạn và một tag mô tả phép biến đổi còn nợ các node con.

Ba thao tác phải được tách rõ:

apply(node, tag): cập nhật ngay thông tin của node theo tag;
compose(oldTag, newTag): gộp hai cập nhật thành một tag tương đương;
push(node): chuyển tag đang nợ xuống hai con rồi xóa tag ở node hiện tại.

Range add và range sum

Nếu cộng $d$ vào mọi phần tử của đoạn có độ dài $len$ , tổng thay đổi thành

sum'=sum+d\cdot len.

Tag cộng hợp thành bằng phép cộng:

lazyAdd'=lazyAdd+d.

apply_add(node, d):
    tree[node].sum += d * tree[node].len
    lazy[node].add += d

Đảo bit trên đoạn

Nếu cnt1 là số bit $1$ trong đoạn, sau khi flip:

cnt1'=len-cnt1.

Hai lần flip triệt tiêu nhau, nên tag có thể hợp thành bằng XOR:

flip'=flip\oplus 1.

Range assignment

Nếu gán mọi phần tử trong đoạn bằng $x$ :

sum'=x\cdot len.

Khác với cộng, phép gán mới thường ghi đè phép gán cũ. Khi cùng tồn tại assign và add, thứ tự rất quan trọng.

Một cách tổ chức an toàn là cho tag chứa:

hasSet;
setValue;
addValue.

Khi áp dụng set(x), ta đặt hasSet=true, setValue=x, đồng thời xóa addValue cũ. Khi áp dụng add(d), nếu đã có set, tăng setValue thêm $d$ ; nếu chưa có set, cộng $d$ vào addValue.

apply_set(node, x):
    tree[node].sum = x * tree[node].len
    lazy[node].hasSet = true
    lazy[node].setValue = x
    lazy[node].addValue = 0

apply_add(node, d):
    tree[node].sum += d * tree[node].len

    nếu lazy[node].hasSet:
        lazy[node].setValue += d
    ngược lại:
        lazy[node].addValue += d

Nhiều trạng thái và tag hoán đổi

Nếu node lưu song song trạng thái cho bit $0$ và bit $1$ , một phép flip thường chỉ cần hoán đổi hai bộ trạng thái. Ví dụ với pref0, suff0, best0 và pref1, suff1, best1, flip có thể đổi toàn bộ nhóm $0$ với nhóm $1$ mà không cần đi xuống lá.

Nếu node lưu số nghịch thế của chuỗi nhị phân, gọi $c_0$ và $c_1$ là số lượng bit $0$ và $1$ . Tổng số cặp khác bit là $c_0c_1$ . Sau flip, số nghịch thế mới là

inv'=c_0c_1-inv.

XOR theo bit

Nếu cập nhật là XOR với một mask, mỗi bit có thể xử lý độc lập. Với bit $b$ , nếu mask có bit $b$ bằng $1$ thì

ones_b'=len-ones_b.

Tag XOR hợp thành cũng bằng XOR.

Lazy đúng khi tree[node] luôn phản ánh đầy đủ mọi cập nhật đã áp dụng cho chính đoạn đó, dù cập nhật chưa được đẩy xuống con. Trước khi đi xuống con để truy vấn hoặc cập nhật chi tiết hơn, phải push.

Giai đoạn 5 - Lazy nâng cao: hàm, đa trường, ma trận và xác suất

Ở mức nâng cao, tag không còn chỉ là một số cộng hay cờ gán. Hãy nhìn tag như một hàm biến đổi tác động lên toàn bộ phần tử hoặc toàn bộ trạng thái của một Node. Khi đó compose chính là phép hợp hàm.

Hàm affine

Một phép cập nhật có dạng

f(x)=ax+b.

Nếu sau đó áp dụng

g(x)=cx+d,

thì phép biến đổi tổng hợp là

g(f(x))=(ca)x+(cb+d).

Nếu tag đang lưu phép cũ $f$ và cập nhật mới là $g$ , phải xác định rõ quy ước compose nghĩa là $g\circ f$ hay $f\circ g$ . Chỉ cần đảo thứ tự một lần là toàn bộ lazy sai.

Với node lưu tổng $S$ của $len$ phần tử:

S'=aS+b\cdot len.

apply_affine(node, a, b):
    tree[node].sum = a * tree[node].sum + b * tree[node].len

compose(old, new):
    // new được áp dụng sau old
    kết quả.a = new.a * old.a
    kết quả.b = new.a * old.b + new.b

Cấp số cộng phụ thuộc vị trí

Nếu cập nhật cộng vào đoạn một cấp số cộng có số hạng đầu $a$ và công sai $d$ , với đoạn dài $len$ thì tổng lượng cộng là

\Delta S=\frac{len\left(2a+(len-1)d\right)}{2}.

Khi đẩy tag sang con phải, số hạng đầu phải được dịch theo độ dài con trái. Nếu con trái có độ dài $L$ thì tag của con phải bắt đầu tại

a'=a+Ld.

Đây là điểm khác biệt cốt lõi giữa lazy phụ thuộc giá trị và lazy phụ thuộc vị trí.

Node có nhiều tổng liên quan

Giả sử mỗi vị trí có hai dãy $A_i,B_i$ và node lưu

S_A=\sum A_i,

S_B=\sum B_i,

S_{AB}=\sum A_iB_i.

Nếu cộng $x$ vào mọi $A_i$ và $y$ vào mọi $B_i$ , thì

S_A'=S_A+x\cdot len,

S_B'=S_B+y\cdot len,

và

S_{AB}'=S_{AB}+xS_B+yS_A+xy\cdot len.

Trong công thức cuối, $S_A,S_B$ phải là giá trị trước cập nhật. Khi code, nên lưu tạm giá trị cũ trước khi sửa node.

Các moment dưới phép affine

Nếu node cần giữ

S_1=\sum x,

S_2=\sum x^2,

S_3=\sum x^3,

và cập nhật $x\mapsto ax+b$ , ta suy ra trực tiếp từ khai triển nhị thức:

S_1'=aS_1+b\cdot len,

S_2'=a^2S_2+2abS_1+b^2\cdot len,

S_3'=a^3S_3+3a^2bS_2+3ab^2S_1+b^3\cdot len.

Tư duy ở đây quan trọng hơn công thức cụ thể: nếu trạng thái của node là các đại lượng tuyến tính hoặc đa thức theo phần tử, hãy dẫn xuất apply bằng đại số trước khi code.

Ma trận và dãy truy hồi

Khi mỗi phần tử có thể biểu diễn bằng vector trạng thái và cập nhật tương ứng với nhân một ma trận chuyển, lazy tag có thể chính là ma trận. Nếu trạng thái là vector $v$ và cập nhật là ma trận $M$ :

v'=Mv.

Hai cập nhật liên tiếp $M_1$ rồi $M_2$ hợp thành thành

M_2M_1.

Vẫn là cùng một nguyên lý hợp hàm, chỉ khác đối tượng là ma trận thay vì cặp hệ số affine.

Kỳ vọng và biến đổi tuyến tính

Một số cập nhật xác suất không cần mô phỏng từng khả năng. Nếu kỳ vọng của mỗi phần tử biến đổi theo

E'=aE+b,

thì có thể dùng đúng khung lazy affine. Khi gặp bài xác suất trên đoạn, nên thử biến đổi công thức kỳ vọng trước khi nghĩ tới cấu trúc phức tạp hơn.

Giai đoạn 6 - Pruning, cập nhật phi tuyến và Segment Tree Beats

Không phải cập nhật đoạn nào cũng có thể biểu diễn bằng một lazy tag đơn giản. Với các phép như modulo, lấy số ước, chmin hoặc chmax, một chiến lược khác là lưu đủ thông tin để biết khi nào cả node không đổi hoặc có thể cập nhật trực tiếp.

Pruning bằng điều kiện bất biến

Giả sử cập nhật là

a_i\leftarrow a_i\bmod x.

Nếu node lưu giá trị lớn nhất mx và

mx<x,

thì mọi phần tử trong node đều bất biến. Có thể bỏ toàn bộ nhánh mà không đi xuống.

update_mod(node, l, r, L, R, x):
    nếu [l, r] không giao [L, R]:
        kết thúc

    nếu tree[node].max < x:
        kết thúc

    nếu l = r:
        cập nhật giá trị lá
        kết thúc

    đi xuống hai con cần thiết
    merge lại node

Một kiểu pruning khác xuất hiện khi phép biến đổi nhanh chóng đưa giá trị về trạng thái ổn định. Node có thể lưu cực trị hoặc một cờ để bỏ qua cả đoạn đã ổn định.

Segment Tree Beats với range chmin

Xét phép

a_i\leftarrow\min(a_i,x).

Nếu chỉ lưu max, ta biết được khi nào bỏ qua nhưng chưa biết khi nào có thể cập nhật cả node. Segment Tree Beats lưu thêm:

max1: giá trị lớn nhất;
max2: giá trị lớn thứ hai phân biệt;
cntMax: số phần tử bằng max1;
sum: tổng đoạn.

Có ba trường hợp.

Nếu

max1\le x,

thì không có gì thay đổi.

Nếu

max2<x<max1,

chỉ các phần tử đang bằng max1 bị hạ xuống $x$ , nên có thể cập nhật cả node:

sum'=sum-(max1-x)\cdot cntMax.

Sau đó đặt

max1=x.

Nếu $x\le max2$ , thay đổi tác động tới nhiều mức giá trị nên phải đẩy xuống con.

range_chmin(node, x):
    nếu node.max1 <= x:
        kết thúc

    nếu node.max2 < x:
        giảm sum theo số phần tử đang bằng max1
        node.max1 = x
        kết thúc

    push(node)
    xử lý hai con
    merge lại node

range chmax đối xứng bằng cách lưu min1, min2, cntMin. Nếu hỗ trợ thêm range add, phép cộng dịch đồng thời các cực trị.

Điểm quan trọng của Beats là độ phức tạp dựa trên phân tích khấu hao, không phải vì từng thao tác luôn chỉ đi qua đúng $O(\log n)$ node. Chỉ nên dùng khi hiểu rõ invariant của các cực trị thứ nhất, thứ hai và điều kiện cập nhật trực tiếp.

Tag là ánh xạ trên tập trạng thái nhỏ

Nếu mỗi giá trị thuộc một miền nhỏ, tag có thể là một ánh xạ

f:\{1,2,\ldots,K\}\to\{1,2,\ldots,K\}.

Hai cập nhật hợp thành bằng hợp hàm ánh xạ. Đây là một mở rộng tự nhiên của lazy: tag không nhất thiết là số, cờ hay ma trận; nó chỉ cần mô tả đủ phép biến đổi và có thể hợp thành hiệu quả.

Giai đoạn 7 - Merge Sort Tree, trục giá trị và Persistent Segment Tree

Giai đoạn này chuyển từ việc mỗi node lưu một giá trị tổng hợp sang việc node có thể lưu cả một cấu trúc nhỏ, hoặc cây có thể giữ nhiều phiên bản theo thời gian.

Merge Sort Tree

Mỗi node lưu các phần tử trong đoạn của nó theo thứ tự tăng dần. Khi build, vector của node cha được tạo bằng cách merge hai vector đã sắp xếp của hai con.

Tổng kích thước của mọi vector là

O(n\log n),

vì mỗi phần tử xuất hiện ở một node trên mỗi tầng của cây.

Một truy vấn đoạn $[L,R]$ được tách thành $O(\log n)$ node. Trong mỗi vector, có thể dùng binary search để đếm số phần tử nhỏ hơn, lớn hơn hoặc nằm trong một khoảng giá trị. Vì vậy truy vấn điển hình có độ phức tạp

O(\log^2 n).

query_count(node, L, R, x):
    tách [L, R] thành các node phủ hoàn toàn

    với mỗi node:
        dùng binary search trong vector đã sắp xếp
        cộng số phần tử thỏa điều kiện

Merge Sort Tree phù hợp khi dữ liệu tĩnh hoặc cập nhật hiếm. Nếu cần cập nhật động mạnh, vector tĩnh trong mỗi node không còn thuận tiện.

Persistent Segment Tree và path copying

Persistent Segment Tree giữ lại các phiên bản cũ sau mỗi cập nhật. Khi cập nhật một vị trí, chỉ các node trên đường từ gốc tới lá thay đổi. Ta tạo node mới cho đường này và tái sử dụng các node không thay đổi.

Mỗi cập nhật tạo

O(\log n)

node mới.

Nếu chỉ sao chép một phiên bản mà chưa cập nhật gì, chỉ cần sao chép con trỏ gốc nên chi phí là $O(1)$ .

update(oldNode, l, r, pos, delta):
    newNode = bản sao của oldNode

    nếu l = r:
        sửa dữ liệu của newNode
        trả newNode

    chỉ tạo mới nhánh chứa pos
    nhánh còn lại tái sử dụng từ oldNode

    merge hai con vào newNode
    trả newNode

Phiên bản prefix và truy vấn k-th

Sau khi nén giá trị, ta có thể xây root[i] biểu diễn histogram của prefix $1..i$ . Mỗi lần thêm $a_i$ , cập nhật tần suất tại giá trị tương ứng.

Histogram của đoạn $[l,r]$ bằng hiệu giữa hai phiên bản:

root[r]-root[l-1].

Để tìm phần tử nhỏ thứ $k$ , tại mỗi node ta tính số phần tử thuộc nửa trái:

$$leftCount=count(root[r].left)-count(root[l-1].left).$$

Nếu $k\le leftCount$ , đi trái. Ngược lại đi phải với

k'=k-leftCount.

kth(rootR, rootLMinus1, l, r, k):
    nếu l = r:
        trả giá trị tương ứng

    leftCount = count(rootR.left) - count(rootLMinus1.left)

    nếu k <= leftCount:
        đi xuống hai root con trái
    ngược lại:
        đi xuống hai root con phải với k - leftCount

Độ phức tạp truy vấn là

O(\log M),

với $M$ là kích thước miền giá trị sau nén.

Persistence trên cây

Nếu mỗi đỉnh $v$ của một cây gốc có một persistent root biểu diễn histogram trên đường từ gốc tới $v$ , thì histogram của đường $u\leftrightarrow v$ có thể kết hợp từ bốn phiên bản. Gọi $w=LCA(u,v)$ , ta dùng dạng:

root_u+root_v-root_w-root_{parent(w)}.

Công thức này là phiên bản theo vertex. Nếu cách gán dữ liệu nằm trên cạnh, biểu thức phải điều chỉnh theo quy ước ánh xạ cạnh vào đỉnh.

Giai đoạn 8 - Euler Tour và Heavy-Light Decomposition

Segment Tree vốn làm việc tốt trên một trục tuyến tính. Với cây, mục tiêu là biến truy vấn cây thành một hoặc nhiều đoạn trên mảng.

Euler Tour cho subtree

Trong DFS, ghi thời điểm vào tin[v]. Sau khi duyệt xong toàn bộ subtree của $v$ , ghi tout[v]. Nếu mỗi đỉnh được đưa vào mảng đúng một lần theo thứ tự DFS, các đỉnh trong subtree của $v$ tạo thành một đoạn liên tiếp:

subtree(v)=[tin[v],tout[v]].

Vì vậy truy vấn hoặc cập nhật toàn subtree trở thành truy vấn hoặc cập nhật đoạn.

dfs(v, parent):
    tin[v] = ++timer
    flat[timer] = giá trị của v

    duyệt từng con u của v:
        nếu u khác parent:
            dfs(u, v)

    tout[v] = timer

Sau bước flatten, Segment Tree không cần biết cấu trúc cây ban đầu; nó chỉ làm việc trên mảng flat.

Heavy-Light Decomposition cho path

Một đường đi $u\leftrightarrow v$ thường không tạo thành một đoạn liên tiếp trong Euler order. Heavy-Light Decomposition (HLD) chia cây thành các heavy chain để mỗi đường đi bất kỳ có thể tách thành $O(\log n)$ đoạn liên tiếp.

Các mảng cốt lõi thường gồm:

parent[v];
depth[v];
heavy[v]: con có subtree lớn nhất;
head[v]: đầu chain chứa $v$ ;
pos[v]: vị trí của $v$ trong mảng HLD.

Khi head[u] != head[v], luôn xử lý chain có head sâu hơn rồi nhảy lên cha của đầu chain đó. Khi hai đỉnh đã nằm cùng chain, xử lý đoạn còn lại giữa chúng.

query_path(u, v):
    ans = identity

    trong khi head[u] != head[v]:
        nếu depth[head[u]] < depth[head[v]]:
            đổi u và v

        ans = merge(ans, query(pos[head[u]], pos[u]))
        u = parent[head[u]]

    nếu depth[u] > depth[v]:
        đổi u và v

    ans = merge(ans, query(pos[u], pos[v]))
    trả ans

Nếu mỗi truy vấn Segment Tree tốn $O(\log n)$ và path tách thành $O(\log n)$ chain, độ phức tạp chuẩn là

O(\log^2 n).

Trọng số cạnh

Một cách phổ biến là gán trọng số cạnh $(parent[v],v)$ vào vị trí pos[v]. Khi truy vấn đường giữa $u$ và $v$ , vị trí của LCA không đại diện cho cạnh nào thuộc đường cần tính nên phải loại đúng vị trí này ở đoạn cuối.

Khi phép gộp phụ thuộc hướng

Nếu phép merge không giao hoán, không thể chỉ gom các đoạn HLD theo bất kỳ thứ tự nào. Đường $u\to v$ có hướng, nên cần giữ hai accumulator: một phần đi từ $u$ lên LCA và một phần đi từ LCA xuống $v$ , hoặc dùng reverse cho Node khi đổi hướng.

Tư duy đúng là: HLD chỉ tách đường đi thành các đoạn; thứ tự ghép các đoạn vẫn phải tái tạo đúng thứ tự của đường đi gốc.

Giai đoạn 9 - 2D, miền chỉ số lớn, implicit/dynamic và cấu trúc đặc biệt

Segment Tree hai chiều

Với ma trận, có thể xây Segment Tree theo trục $x$ , và tại mỗi node của trục $x$ lại có một Segment Tree theo trục $y$ . Truy vấn hình chữ nhật và cập nhật điểm đi qua hai tầng logarit, thường có độ phức tạp

O(\log^2 n)

trong trường hợp kích thước hai chiều cùng cỡ $n$ .

Tuy nhiên hằng số và bộ nhớ lớn. Không nên dùng 2D Segment Tree chỉ vì bài có hai tọa độ; nếu phép toán là tổng và chỉ cần point update + rectangle sum, 2D Fenwick thường gọn hơn.

Nén tọa độ

Khi tọa độ lớn nhưng chỉ xuất hiện tại hữu hạn điểm hoặc biên đoạn, nén tọa độ giúp đưa miền về kích thước $O(n)$ . Với bài cập nhật trên đoạn liên tục, không được chỉ giữ các đầu mút rồi coi chúng là những điểm kề nhau nếu giữa hai đầu mút còn một khoảng thật sự cần phân biệt.

Một cách thường dùng là đưa thêm các biên kế cận hoặc lưu độ dài hình học của mỗi khoảng nén. Với sweep line, node không chỉ biết số chỉ số mà phải biết tổng độ dài thật đang được phủ.

Dynamic hoặc Implicit Segment Tree

Nếu miền chỉ số rất lớn, chẳng hạn tới $10^{18}$ , không thể cấp phát toàn bộ cây. Implicit Segment Tree chỉ tạo node khi một truy vấn hoặc cập nhật thực sự đi qua node đó.

Độ sâu phụ thuộc miền tọa độ:

O(\log U),

với $U$ là kích thước miền.

Nếu có $q$ thao tác, số node được tạo thường ở mức

O(q\log U)

trong cận thô, dù thực tế có thể ít hơn do nhiều đường dùng chung node.

update(node, l, r, L, R):
    nếu node chưa tồn tại:
        tạo node rỗng

    nếu [l, r] được phủ hoàn toàn:
        apply cập nhật
        kết thúc

    tạo con khi thực sự cần đi xuống
    push nếu có lazy
    cập nhật các con giao với [L, R]
    merge lại node

Trạng thái đặc biệt theo tầng

Một số bài không thay đổi giá trị từng lá mà thay đổi cách diễn giải thứ tự các nửa ở từng tầng, chẳng hạn đảo block hoặc hoán đổi hai con theo mask. Khi đó không nhất thiết phải rebuild cây. Có thể lưu một mask trạng thái theo tầng và trong lúc truy vấn/cập nhật quyết định con logic nào tương ứng với con vật lý nào.

Mẫu tư duy là phân biệt dữ liệu của cây với cách ánh xạ chỉ số vào cây. Nếu chỉ ánh xạ thay đổi, hãy thử biến đổi đường đi thay vì sửa toàn bộ node.

Giai đoạn 10 - Segment Tree trên trục thời gian và rollback

Một kỹ thuật offline mạnh là dùng Segment Tree không phải trên chỉ số mảng mà trên thời gian. Mỗi lá đại diện cho một thời điểm truy vấn. Một đối tượng tồn tại trong một khoảng thời gian sẽ được gắn vào các node phủ khoảng đó.

Giả sử một cạnh hoạt động trong khoảng thời gian $[L,R)$ . Ta thêm cạnh vào $O(\log Q)$ node của Segment Tree thời gian, với $Q$ là số mốc thời gian.

Khi DFS cây thời gian:

ghi lại snapshot trạng thái hiện tại;
áp dụng mọi đối tượng gắn tại node;
nếu là lá, trả lời truy vấn tại thời điểm đó;
nếu chưa là lá, đi xuống hai con;
rollback về snapshot trước khi rời node.

dfs_time(node, l, r):
    snapshot = kích thước stack rollback

    với mỗi sự kiện gắn tại node:
        apply sự kiện vào cấu trúc trạng thái

    nếu l = r:
        trả lời truy vấn tại thời điểm l
    ngược lại:
        dfs_time(con trái)
        dfs_time(con phải)

    rollback về snapshot

Rollback DSU

DSU rollback thường dùng union by size nhưng không dùng path compression, vì path compression thay đổi nhiều con trỏ cha và khó hoàn tác gọn.

Mỗi lần union, lưu lên stack đủ dữ liệu để khôi phục:

root nào bị gắn;
parent cũ;
size cũ của root còn lại;
các đại lượng phụ nếu có.

Một lần rollback chỉ cần đảo ngược các thay đổi kể từ snapshot.

Nếu trạng thái còn chứa khoảng cách XOR, parity hoặc linear basis của chu trình, nguyên lý vẫn không đổi: mọi thay đổi phải được ghi lại để có thể hoàn tác đúng khi DFS quay lui.

Nếu có $K$ khoảng tồn tại, mỗi khoảng được đưa vào $O(\log Q)$ node thời gian. Phần chi phí chính vì thế thường tỉ lệ với

O(K\log Q)

lần áp dụng sự kiện, nhân thêm chi phí của cấu trúc rollback bên dưới.

Giai đoạn 11 - Kết hợp DP, đồ thị, sweep line và mô hình hóa

Ở giai đoạn này Segment Tree thường không phải ý tưởng chính. Nó là một engine truy vấn giúp tăng tốc một chuyển trạng thái, một phép quét hoặc một mô hình đã được biến đổi đúng.

DP theo trục giá trị

Nếu chuyển trạng thái có dạng

dp[i]=value_i+\max_{x\in S_i}best[x],

và $S_i$ là một hoặc vài khoảng trên trục giá trị, có thể nén tọa độ rồi dùng Segment Tree để lấy max trên các khoảng đó. Sau khi tính $dp[i]$ , cập nhật chmax tại vị trí đại diện cho giá trị của phần tử hiện tại.

với từng trạng thái i theo đúng thứ tự DP:
    bestPrev = query các khoảng giá trị hợp lệ
    dp[i] = value[i] + bestPrev
    update_chmax(vị trí giá trị của i, dp[i])

Nếu cần truy vết, Node có thể lưu cả giá trị tốt nhất và chỉ số tạo ra giá trị đó.

Quét đường thẳng và hợp hình chữ nhật

Với diện tích hợp của nhiều hình chữ nhật, tạo sự kiện tại hai biên $x$ . Sau khi nén trục $y$ , Segment Tree duy trì tổng độ dài $y$ đang được phủ.

Nếu hai sự kiện liên tiếp có hoành độ $x_{prev}$ và $x$ , diện tích tăng thêm

area+=coveredLength\cdot(x-x_{prev}).

Node thường lưu coverCount. Nếu coverCount>0, toàn bộ đoạn của node đang được phủ và coveredLength bằng độ dài hình học của đoạn. Nếu coverCount=0, coveredLength bằng tổng của hai con.

sắp xếp sự kiện theo x

với mỗi nhóm sự kiện tại cùng x:
    area += root.coveredLength * (x - previousX)

    áp dụng toàn bộ sự kiện add/remove trên trục y
    previousX = x

Để tính chu vi thay vì diện tích, node cần thêm thông tin như số component phủ liên tiếp và trạng thái phủ ở hai biên. Đây là ví dụ điển hình của việc mở rộng Node theo đúng đại lượng hình học cần tính.

Đồ thị có cạnh tới cả một đoạn

Nếu một thao tác tạo cạnh từ một đỉnh tới mọi đỉnh trong đoạn, thêm từng cạnh riêng lẻ có thể quá lớn. Có thể dùng các node của Segment Tree như các đỉnh phụ trong đồ thị.

Một cây có hướng từ node cha xuống con giúp biểu diễn cạnh từ một đỉnh tới một đoạn. Một cây hướng ngược từ con lên cha giúp biểu diễn cạnh từ một đoạn tới một đỉnh. Một đoạn bất kỳ được phân rã thành $O(\log n)$ node cây, nên mỗi cạnh dạng đỉnh-đoạn hoặc đoạn-đỉnh chỉ cần $O(\log n)$ cạnh phụ.

Sau khi dựng đồ thị mở rộng, thuật toán đường đi ngắn vẫn chạy trên đồ thị đó như bình thường. Segment Tree ở đây không dùng để query; nó dùng để nén một họ cạnh có cấu trúc.

Theo dõi lần xuất hiện gần nhất

Nhiều bài về phần tử phân biệt, mex hoặc chi phí đoạn có thể chuyển thành việc theo dõi last occurrence hay previous occurrence. Khi quét biên phải của đoạn, mỗi giá trị mới chỉ làm thay đổi một khoảng trạng thái liên quan đến lần xuất hiện trước của nó. Segment Tree giữ min, max hoặc DP của các trạng thái đó.

Mấu chốt không phải là thấy "đoạn" rồi lập tức dùng Segment Tree. Trước hết phải chọn đúng trục quét và biểu thức trạng thái để một bước quét chỉ gây ra vài cập nhật đoạn có cấu trúc.

Mảng vòng

Một kỹ thuật thường gặp là nhân đôi mảng để biến đoạn vòng thành đoạn thường. Sau đó Segment Tree xử lý trên mảng độ dài $2n$ , còn phần mô hình hóa đảm bảo chỉ lấy các đoạn có độ dài hợp lệ.

Giai đoạn này cần giữ một nguyên tắc: nếu không thể mô tả rõ dữ liệu nào đang nằm trong Node và vì sao một phép query đúng là thứ DP, sweep line hoặc đồ thị cần, thì Segment Tree chưa phải phần cần code đầu tiên.

Giai đoạn 12 - Ranh giới: khi Segment Tree không phải lựa chọn tự nhiên

Segment Tree rất tổng quát, nhưng tổng quát không đồng nghĩa với tối ưu cho mọi bài. Kỹ năng thực chiến quan trọng là nhận ra khi cấu trúc đơn giản hơn cho cùng độ phức tạp hoặc thậm chí tốt hơn.

Với mảng tĩnh và truy vấn tổng đoạn, prefix sum cho phép tiền xử lý $O(n)$ và trả lời mỗi truy vấn trong

O(1).

Với mảng tĩnh và truy vấn min hoặc max, Sparse Table tiền xử lý

O(n\log n)

và trả lời truy vấn idempotent trong

O(1).

Với point update và prefix/range sum, Fenwick Tree thường ngắn hơn Segment Tree nhưng vẫn đạt

O(\log n)

cho cập nhật và truy vấn.

Range add + point query có thể chuyển bằng mảng hiệu hoặc Fenwick. Nếu cập nhật cộng $x$ trên $[l,r]$ , trên mảng hiệu ta thực hiện:

d[l]+=x,

d[r+1]-=x.

Giá trị tại một điểm trở thành prefix sum của mảng hiệu.

Các bài chọn phần tử theo thứ hạng trên một bảng tần suất cũng có thể dùng Fenwick bằng kỹ thuật tìm theo prefix sum. Các truy vấn offline về số phần tử phân biệt thường có lời giải gọn bằng cách quét truy vấn kết hợp Fenwick hoặc dùng Mo's algorithm. Các cập nhật kiểu "gán mỗi vị trí chưa xử lý đúng một lần" có thể phù hợp với DSU next-pointer để nhảy qua vị trí đã hoàn tất.

Trong hai chiều, nếu chỉ cần point update và rectangle sum, 2D Fenwick thường phù hợp hơn 2D Segment Tree. Ngược lại, khi cần custom Node, lazy phức tạp, tree walking, persistence hoặc phép gộp không thể biểu diễn thuận tiện bằng Fenwick, Segment Tree mới thể hiện rõ lợi thế.

Cách chọn cấu trúc nên xuất phát từ đúng cặp thao tác của đề: dữ liệu tĩnh hay động, cập nhật điểm hay đoạn, truy vấn có nghịch đảo hay không, phép gộp có kết hợp hay không, có cần tìm vị trí bằng cách đi xuống cây hay giữ nhiều phiên bản hay không. Segment Tree là công cụ rất mạnh, nhưng phản xạ tốt nhất là dùng nó khi cấu trúc thông tin của bài thực sự cần sức mạnh đó.

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000001 Truy vấn tổng đoạn động (Dynamic Range Sum Queries)	0	0	1
SGM0000002 Truy vấn giá trị nhỏ nhất động (Dynamic Range Minimum Queries)	0	0	1
SGM0000003 Biến trở (Potentiometers)	0	0	1
SGM0000004 RMQ với phép dịch vòng (RMQ with Shifts)	0	0	1
SGM0000005 Dấu của tích trên đoạn (Interval Product)	0	0	1
SGM0000006 Xenia và các phép toán bit (Xenia and Bit Operations)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000007 Tổng hai phần tử lớn nhất (Maximum Sum)	0	0	1
SGM0000008 Giá trị xuất hiện nhiều nhất (Frequent Values)	0	0	1
SGM0000009 Đàn kiến (Ant Colony)	0	0	1
SGM0000010 Sereja và dãy ngoặc (Sereja and Brackets)	0	0	1
SGM0000011 Truy vấn tổng đoạn con lớn nhất I (Can you answer these queries I)	0	0	1
SGM0000012 Truy vấn tổng đoạn con lớn nhất III (Can you answer these queries III)	0	0	1
SGM0000013 Truy vấn tổng tiền tố (Prefix Sum Queries)	0	0	1
SGM0000014 Truy vấn tổng đoạn con (Subarray Sum Queries)	0	0	1
SGM0000015 Bash và bài toán GCD khó (Bash and a Tough Math Puzzle)	0	0	1
SGM0000016 Truy vấn cửa hàng pizza (Pizzeria Queries)	0	0	1
SGM0000017 Gán điểm và hợp thành hàm trên đoạn (Point Set Range Composite)	0	0	1
SGM0000018 Kiểm tra dãy ngoặc (Parenthesis Checking)	0	0	1
SGM0000019 Trình soạn thảo (Editor)	0	0	1
SGM0000020 Cân bằng (Equilibrium)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000021 Phân phòng khách sạn (Hotel Queries)	0	0	1
SGM0000022 Xóa phần tử khỏi danh sách (List Removals)	0	0	1
SGM0000023 Deda (Deda)	0	0	1
SGM0000024 Tập hợp thứ tự (Order statistic set)	0	0	1
SGM0000025 Các điểm (Points)	0	0	1
SGM0000026 Truy vấn lương (Salary Queries)	0	0	1
SGM0000027 Cây đoạn (Segment Tree)	0	0	1
SGM0000028 Khách sạn (Hotel)	0	0	1
SGM0000029 Bình hoa và hoa (Vases and Flowers)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000030 Truy vấn khủng khiếp (Horrible Queries)	0	0	1
SGM0000031 Bật tắt đèn (Light Switching)	0	0	1
SGM0000032 Bội số của 3 (Multiples of 3)	0	0	1
SGM0000033 RMQ vòng tròn (Circular RMQ)	0	0	1
SGM0000034 A-hoy, Cướp biển! (Ahoy, Pirates!)	0	0	1
SGM0000035 Cập nhật đoạn và tổng (Range Updates and Sums)	0	0	1
SGM0000036 XOR trên đoạn (XOR on Segment)	1	1	1
SGM0000037 Truy vấn may mắn (Lucky Queries)	0	0	1
SGM0000038 Tổng bình phương với cây đoạn (Sum of Squares with Segment Tree)	0	0	1
SGM0000039 Đường chân trời (SKYLINE)	0	0	1
SGM0000040 Biến đổi affine và tổng đoạn (Range Affine Range Sum)	0	0	1
SGM0000041 Mảng thú vị (Interesting Array)	0	0	1
SGM0000042 Truy vấn kỳ nghỉ (Vacation Query)	0	0	1
SGM0000043 Đảo bit và nghịch thế (Lazy Segment Tree)	0	0	1
SGM0000044 Sao chép dữ liệu (Copying Data)	0	0	1
SGM0000045 Phép toán trên dãy (Sequence operation)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000046 Truy vấn đa thức (Polynomial Queries)	0	0	1
SGM0000047 Kefa và chiếc đồng hồ (Kefa and Watch)	0	0	1
SGM0000048 Một nhiệm vụ đơn giản (A Simple Task)	0	0	1
SGM0000049 Hoán vị bảng chữ cái (Alphabet Permutations)	0	0	1
SGM0000050 Nhắm mắt (Eyes Closed)	0	0	1
SGM0000051 Lại thêm truy vấn trên mảng (Please, another Queries on Array?)	0	0	1
SGM0000052 DZY yêu số Fibonacci (DZY Loves Fibonacci Numbers)	0	0	1
SGM0000053 Sasha và mảng (Sasha and Array)	0	0	1
SGM0000054 Truy vấn hai dãy (Two Sequence Queries)	0	0	1
SGM0000055 Biến đổi (Transformation)	0	0	1
SGM0000056 Truy vấn cập nhật ngẫu nhiên (Random Update Query)	0	0	1
SGM0000057 Gán đoạn và hợp thành hàm trên đoạn (Range Set Range Composite)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000058 Đứa trẻ và dãy số (The Child and Sequence)	0	0	1
SGM0000059 Tổng và thay thế (SUM and REPLACE)	0	0	1
SGM0000060 Mảng may mắn (Lucky Array)	0	0	1
SGM0000061 Chmin Chmax Add và tổng đoạn (Range Chmin Chmax Add Range Sum)	0	0	1
SGM0000062 Dãy tuyệt đẹp (Gorgeous Sequence)	0	0	1
SGM0000063 DZY yêu màu sắc (DZY Loves Colors)	0	0	1
SGM0000064 Truy vấn đổi hàng loạt (Mass Change Queries)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000065 Truy vấn k (K-query)	0	0	1
SGM0000066 Truy vấn khoảng giá trị (Range Interval Queries)	0	0	1
SGM0000067 Truy vấn k trực tuyến (K-Query Online)	0	0	1
SGM0000068 Số nhỏ thứ k (K-th Number)	0	0	1
SGM0000069 Số nhỏ thứ k (K-th Number)	0	0	1
SGM0000070 Super Mario (Super Mario)	0	0	1
SGM0000071 Truy vấn đoạn và bản sao (Range Queries and Copies)	0	0	1
SGM0000072 Đếm trên cây (Count on a tree)	0	0	1
SGM0000073 Xây dựng quân đội (Army Creation)	0	0	1
SGM0000074 Tấm biển trên hàng rào (Sign on Fence)	0	0	1
SGM0000075 Một lần xuất hiện (One Occurrence)	0	0	1
SGM0000076 Truy vấn giá trị phân biệt II (Distinct Values Queries II)	0	0	1
SGM0000077 Truy vấn tổng xu bị thiếu (Missing Coin Sum Queries)	0	0	1

mở rộng thu gọn

Bài toán	Tried	AC	Độ khó
SGM0000078 Truy vấn cây con (Subtree Queries)	0	0	1
SGM0000079 Truy vấn đường đi từ gốc (Path Queries)	0	0	2
SGM0000080 Truy vấn đường đi II (Path Queries II)	0	0	1
SGM0000081 Gán hàm tại đỉnh, hợp hàm trên đường đi (Vertex Set Path Composite)	0	0	2
SGM0000082 Truy vấn trên cây (Query on a tree)	0	0	1
SGM0000083 Truy vấn trên cây lần nữa (Query on a tree again!)	0	0	2
SGM0000084 Bạn có trả lời được các truy vấn VII (Can you answer these queries VII)	0	0	2
SGM0000085 Cây nước (Water Tree)	0	0	2
SGM0000086 Cây năm mới (New Year Tree)	0	0	2
SGM0000087 Danil và công việc bán thời gian (Danil and a Part-time Job)	0	0	2
SGM0000088 Thay đổi trên cây (On Changing Tree)	0	0	2

Người tham gia: 1
Tạo bởi: Phước Hưng