Segment Tree: cập nhật điểm, truy vấn tổng và min trên đoạn

Khi prefix sum không còn thuận tiện

Trên mảng không đổi, prefix sum trả tổng đoạn nhanh sau tiền xử lý. Nhưng nếu thay một phần tử, nhiều tổng tiền tố phía sau phải đổi. Làm lại toàn bộ sau mỗi cập nhật có thể tốn O(n) mỗi lần, không phù hợp khi cập nhật và truy vấn xen kẽ nhiều.

Segment Tree chia mảng thành các đoạn nhỏ. Thay một lá chỉ ảnh hưởng những nút tổ tiên chứa nó, có số lượng theo chiều cao cây. Khi hỏi một đoạn, ta ghép một số đoạn đã lưu thay vì quét mọi phần tử bên trong. Cùng khung này có thể lưu min, max hoặc thông tin phức tạp hơn nếu phép gộp phù hợp.

Đoạn nửa mở [1,4) chứa các vị trí 1,2,3. Viết rõ quy ước này giúp tránh một lỗi tưởng như nhỏ nhưng làm mọi kết quả lệch ở biên. Nếu đề nhập đoạn đóng [L,R] đánh số từ 1, phải chuyển tương ứng sang [L−1,R) trước khi gọi hàm.

Một nút giữ cặp tổng và min

Với một đoạn, lưu Node=(sum,minimum). Gộp hai con bằng tổng hai sum và min hai minimum. Nếu con trái có (6,1), con phải có (6,2), cha là (12,1). Lá mang giá trị x giữ cặp (x,x).

Phép gộp phải có tính kết hợp để đổi cách đặt ngoặc các đoạn mà vẫn giữ kết quả: gộp (A,B) rồi C giống gộp A với (B,C). Không cần mọi phép gộp đều là cộng, nhưng phải định nghĩa trạng thái đủ và đúng cho mục tiêu cần hỏi.

Phần tử trung hòa là (0,INF): gộp nó vào một đoạn không đổi sum hoặc min. Không dùng (0,0) khi dữ liệu min có thể dương, vì giá trị 0 giả sẽ thắng mọi phần tử thật. Với max, phần tử trung hòa lại phải dùng dấu rất nhỏ thay cho INF dương.

Bố trí cây trong mảng và đệm lá

Code chọn base là lũy thừa của 2 nhỏ nhất không bé hơn số phần tử. Các lá nằm từ tree[base] trở đi; các lá thừa giữ trung hòa. Nút p có hai con 2p và 2p+1. Điền lá rồi gộp từ p=base−1 giảm tới 1 để dựng cả cây.

Với n=5, base=8. Gốc đại diện [0,8), con trái [0,4), con phải [4,8). Những vị trí 5,6,7 không phải dữ liệu thật nên không được cập nhật hoặc hỏi như phần tử input; chúng chỉ giúp bố trí cây cân bằng. Trung hòa bảo đảm phần đệm không làm đổi tổng/min của dữ liệu thật khi gộp.

Có cách cài dùng đúng 2n ô mà không đệm lũy thừa hai, nhưng bố trí đoạn trong cây có chi tiết khác khi n không là lũy thừa hai. Hãy giữ một mô hình khớp với code đang học; ví dụ ở đây đã đệm để các nút dễ liên hệ với hình chia đôi khoảng.

Cập nhật gán một phần tử

Muốn đặt a[i]=value, thay lá i+base bằng (value,value). Sau đó đi lên cha bằng chia 2, mỗi lần gộp lại từ hai con. Chỉ các đoạn chứa i đổi giá trị; những nhánh khác vẫn đúng và không cần đụng tới.

Trong ví dụ, gán vị trí 2 từ 4 thành −2. Mảng thành [5,1,−2,2,3], tổng 9 và min −2. Đừng cộng value vào lá nếu lệnh là gán; nếu đề cho cộng delta thì cần lấy giá trị cũ rồi cộng hoặc thiết kế một thao tác add riêng.

Một cập nhật điểm đi qua O(log n) nút. Điều này khác duyệt toàn bộ các lá của một đoạn dài để cập nhật mỗi điểm: lặp cách đó cho cả đoạn không còn O(log n) theo độ dài truy vấn. Lazy propagation xử lý kiểu cập nhật đoạn phù hợp ở bài sau.

Truy vấn bằng hai đầu l,r

Dịch l,r tới tầng lá. Khi l là con phải, đoạn của nó nằm trọn phần cần lấy mà không thể gộp cùng anh em phía trái, nên nhận tree[l] rồi tăng l. Khi r là biên phải lẻ, giảm r trước rồi nhận tree[r]. Sau đó đưa cả hai lên cha và tiếp tục tới khi hai biên gặp nhau.

Tại mỗi tầng, chỉ nhận một số nút sát hai biên; phần giữa được gộp thành các đoạn lớn hơn ở tầng trên. Do chiều cao O(log n), truy vấn cũng O(log n), kể cả khi đoạn cần hỏi dài gần n. Đoạn rỗng [i,i) trả trung hòa: tổng 0 và min INF.

Code dùng một bộ tích lũy vì sum và min ở đây còn giao hoán. Nếu đổi Node sang ghép xâu, nhân ma trận hoặc một phép kết hợp không giao hoán, cần giữ đúng thứ tự các đoạn, thường dùng hai bộ tích lũy trái/phải. Tính kết hợp không cho phép đảo thứ tự tùy ý.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
const long long INF=1LL<<60;
using Node=pair<long long,long long>;
Node merge_node(Node a,Node b){return {a.first+b.first,min(a.second,b.second)};}
class SegmentTree{
    int n;vector<Node> tree;
public:
    explicit SegmentTree(const vector<long long>& a):n(1){
        while(n<(int)a.size())n*=2;
        tree.assign(2*n,{0,INF});
        for(int i=0;i<(int)a.size();++i)tree[n+i]={a[i],a[i]};
        for(int i=n-1;i>0;--i)tree[i]=merge_node(tree[2*i],tree[2*i+1]);
    }
    void assign(int i,long long value){
        int p=i+n;tree[p]={value,value};
        for(p/=2;p>0;p/=2)tree[p]=merge_node(tree[2*p],tree[2*p+1]);
    }
    Node query(int left,int right)const{
        Node result={0,INF};
        for(left+=n,right+=n;left<right;left/=2,right/=2){
            if(left&1)result=merge_node(result,tree[left++]);
            if(right&1)result=merge_node(result,tree[--right]);
        }
        return result;
    }
};
void print(Node x){cout<<x.first<<' ';if(x.second==INF)cout<<"INF\n";else cout<<x.second<<'\n';}
int main(){
    int n,q;
    if(cin>>n>>q){
        vector<long long>a(n);for(auto& x:a)cin>>x;SegmentTree t(a);
        for(int z=0;z<q;++z){char op;int l;long long r;cin>>op>>l>>r;
            if(op=='S')t.assign(l,r);else print(t.query(l,(int)r));}
    }else{
        SegmentTree t({5,1,4,2,3});print(t.query(1,4));t.assign(2,-2);print(t.query(0,5));
    }
}

import sys
INF=1<<60

def merge(a,b):
    return a[0]+b[0],min(a[1],b[1])

class SegmentTree:
    def __init__(self,a):
        self.n=1
        while self.n<len(a):
            self.n*=2
        n=self.n
        self.tree=[(0,INF)]*(2*n)
        for i,x in enumerate(a):
            self.tree[n+i]=(x,x)
        for i in range(n-1,0,-1):
            self.tree[i]=merge(self.tree[2*i],self.tree[2*i+1])

    def assign(self,i,value):
        p=i+self.n;self.tree[p]=(value,value);p//=2
        while p:
            self.tree[p]=merge(self.tree[2*p],self.tree[2*p+1]);p//=2

    def query(self,left,right):
        result=(0,INF);left+=self.n;right+=self.n
        while left<right:
            if left&1:
                result=merge(result,self.tree[left]);left+=1
            if right&1:
                right-=1;result=merge(result,self.tree[right])
            left//=2;right//=2
        return result

def show(x):
    print(x[0],'INF' if x[1]==INF else x[1])

if __name__=='__main__':
    lines=sys.stdin.read().splitlines()
    if lines:
        n,q=map(int,lines[0].split());a=list(map(int,lines[1].split()));t=SegmentTree(a)
        for line in lines[2:2+q]:
            op,l,r=line.split();l=int(l);r=int(r)
            if op=='S':
                t.assign(l,r)
            else:
                show(t.query(l,r))
    else:
        t=SegmentTree([5,1,4,2,3]);show(t.query(1,4));t.assign(2,-2);show(t.query(0,5))

Không nhập dữ liệu, chương trình in 7 1, gán a[2]=−2 rồi in 9 -2. Input riêng có n,q, một dòng n giá trị, tiếp theo q lệnh. S i value gán điểm, Q l r hỏi tổng và min trên [l,r). n dương, các chỉ số và biên hợp lệ; l có thể bằng r để hỏi đoạn rỗng.

INF bằng 2 mũ 60 nên mọi giá trị dùng cho min phải nhỏ hơn INF; các tổng trung gian C++ phải vừa long long. Ví dụ, n không quá 100.000 và trị tuyệt đối các phần tử sau cập nhật không quá một tỷ là một miền số học an toàn. Đây là minh họa cách kiểm kiểu số, không phải bảo đảm hiệu năng theo một hệ thống chấm cụ thể.

Python đọc mảng trên một dòng rồi mỗi lệnh một dòng như mô tả. Nếu đề cho cách xuống dòng khác hoặc chấm hàm, điều chỉnh phần giao tiếp; không thay ý nghĩa [l,r) bên trong mà quên đổi các lệnh nhập.

Độ phức tạp và lựa chọn cấu trúc

Vì base nhỏ hơn 2n khi n dương, dựng cây từ lá cần O(n) thời gian và O(n) bộ nhớ. Mỗi gán điểm hoặc hỏi đoạn cần O(log n). Node của ví dụ giữ hai số, nên lưu tổng và min cùng nhau vẫn là trạng thái kích thước hằng.

Không phải cứ một cấu trúc tổng quát hơn là lựa chọn tốt hơn. Prefix sum có thể đơn giản nhất khi dữ liệu tĩnh; Fenwick thường gọn cho tổng. Segment Tree hữu ích khi thông tin cần gộp phong phú hơn hoặc phép truy vấn không có phép nghịch đảo như lấy hiệu hai tiền tố.

Node cho tổng đoạn con lớn nhất cần nhiều thông tin hơn

Nếu hỏi tổng lớn nhất của một đoạn con nằm trong khoảng, chỉ giữ tổng toàn khoảng và max phần tử là chưa đủ. Lời giải tốt nhất có thể nằm ở trái, phải hoặc băng qua giữa. Một thiết kế thường giữ tổng, prefix tốt nhất, suffix tốt nhất và best toàn đoạn, rồi gộp đúng từng trường.

Điều này lặp lại bài học của DP trên cây: cha cần đủ thông tin ở ranh giới để nối hai lời giải con. Đừng chỉ giữ “đáp án tốt nhất” nếu các phương án băng qua ranh giới cần thêm trạng thái. Bài nâng cao trong phần luyện giúp quan sát lý do phải mở rộng Node.

Kiểm bằng mảng thường

Để tự kiểm tra cây phân đoạn, bạn có thể duy trì song song một mảng thường, thực hiện gán trực tiếp và quét tổng/min trên từng đoạn để đối chiếu kết quả. Hãy thử n = 1, các kích thước 3, 5, 7, 9 không phải lũy thừa của 2, số âm, gán đè nhiều lần tại cùng vị trí và truy vấn đoạn rỗng.

Tự thử đoạn chỉ một phần tử, toàn mảng, biên kết thúc đúng n và gán giá trị nhỏ nhất rồi gán lớn trở lại. Những ca này kiểm cả phần đệm, trung hòa và cập nhật cha; chỉ hỏi toàn mảng sau một thay đổi có thể bỏ sót lỗi chọn nút ở hai biên.

Luyện ngay trên Big-O Coding

Bài cập nhật và min luyện khung cơ bản. Bài max đổi trường thông tin cùng trung hòa tương ứng. Tổng đoạn con lớn nhất là bước nâng cao về thiết kế Node; hãy chứng minh công thức gộp prefix, suffix, best trước khi dùng lại phần đi cây.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Segment Tree
• USACO Guide: Point Update Range Sum
• C++ reference: vector