Fenwick Tree: lowbit, cập nhật điểm và tổng đoạn

Một cấu trúc gọn cho tổng thay đổi theo thời gian

Prefix sum giải tổng đoạn trên mảng tĩnh rất thuận tiện, nhưng thay một phần tử có thể ảnh hưởng nhiều tổng phía sau. Fenwick giữ các tổng nhóm nhỏ được tổ chức bằng bit, để một cập nhật chỉ sửa O(log n) ô và một tiền tố cũng ghép được từ O(log n) nhóm.

Ví dụ a=[2,1,3,4,5]. Tổng [1,4) là 1+3+4=8. Cộng 2 vào vị trí 2 làm mảng thành [2,1,5,4,5], tổng toàn mảng từ 15 thành 17. Đây là hai thao tác mặc định của code bên dưới.

Fenwick thường ngắn hơn Segment Tree cho tổng điểm/đoạn, nhưng ngắn không có nghĩa phù hợp mọi phép toán. Cách lấy hiệu hai tiền tố dựa vào tính chất của phép cộng; trước khi thay tổng bằng thống kê khác, phải kiểm lại phần toán học.

lowbit chỉ ra độ dài vùng đang giữ

Với số nguyên dương i, lowbit(i)=i & (−i) lấy giá trị của bit 1 thấp nhất. Các giá trị đầu là lowbit(1)=1, lowbit(2)=2, lowbit(3)=1, lowbit(4)=4, lowbit(5)=1, lowbit(6)=2. Nhìn ở dạng nhị phân giúp thấy vì sao mỗi vị trí đại diện một độ dài là lũy thừa hai.

Ở cách cài dùng bit từ 1, bit[i] giữ tổng các vị trí mảng gốc trong đoạn [i−lowbit(i),i), với mảng gốc từ 0. Ví dụ bit[4] giữ bốn phần tử a[0] tới a[3]; bit[3] chỉ giữ a[2]. Đây không phải mảng tổng tiền tố đầy đủ ở mọi ô.

Mỗi phần tử xuất hiện trong nhiều vùng lớn nhỏ phù hợp. Cập nhật đi tới những vùng chứa nó; truy vấn đi lùi qua những vùng không giao nhau để phủ đúng tiền tố cần hỏi.

Truy vấn tiền tố: xóa dần bit 1 thấp nhất

Muốn tổng [0,end), đặt i=end. Cộng bit[i], rồi cho i giảm lowbit(i), lặp tới 0. Mỗi bước bỏ vùng ở cuối tiền tố còn lại. Vì các vùng được ghép kề nhau và không chồng, không phần tử nào bị bỏ sót hoặc tính hai lần.

Với end=5, nhận bit[5]=5 cho [4,5), giảm i từ 5 về 4; nhận bit[4]=10 cho [0,4), rồi về 0. Tổng 15. Với end=3, ghép bit[3]=3 và bit[2]=3, tổng 6 bằng 2+1+3.

Để hỏi [l,r), lấy prefix(r) trừ prefix(l). Phần [0,l) xuất hiện trong cả hai nên bị loại, còn đúng đoạn l tới r−1. Với [1,4), prefix(4)=10, prefix(1)=2, hiệu 8. Đoạn rỗng có hai tiền tố bằng nhau nên trả 0 tự nhiên.

Cộng một điểm: đi tới những vùng cha chứa nó

Giao tiếp nhận index từ 0, chuyển vào bit bằng i=index+1. Cộng delta vào bit[i], rồi cho i tăng lowbit(i), tiếp tục khi còn trong n. Dãy chỉ số này đi qua các nhóm tổng cần phản ánh thay đổi của phần tử đó.

Cộng 2 vào a[2] bắt đầu i=3. bit[3] từ 3 thành 5, sau đó i=4 làm bit[4] từ 10 thành 12, rồi i=8 vượt n=5 và dừng. bit[5] không đổi vì vùng [4,5) không chứa vị trí 2. Tổng [0,5) mới là bit[5]+bit[4]=5+12=17.

Không bắt đầu vòng nội bộ ở i=0: lowbit(0)=0 nên i không tiến lên và có thể lặp vô hạn. Việc cộng 1 vào chỉ số giao tiếp chính là một phần của cách cài từ 1, không phải một dòng có thể bỏ tùy ý.

Code C++ và Python

#include <iostream>
#include <vector>
using namespace std;
class Fenwick{
    int n;vector<long long> bit;
public:
    explicit Fenwick(const vector<long long>& a):n(a.size()),bit(n+1,0){
        for(int i=0;i<n;++i)add(i,a[i]);
    }
    void add(int index,long long delta){for(int i=index+1;i<=n;i+=i&-i)bit[i]+=delta;}
    long long prefix(int end)const{long long sum=0;for(int i=end;i>0;i-=i&-i)sum+=bit[i];return sum;}
    long long sum(int left,int right)const{return prefix(right)-prefix(left);}
};
int main(){
    int n,q;
    if(cin>>n>>q){
        vector<long long>a(n);for(auto& x:a)cin>>x;Fenwick t(a);
        for(int z=0;z<q;++z){char op;int l;long long r;cin>>op>>l>>r;
            if(op=='A')t.add(l,r);else cout<<t.sum(l,(int)r)<<'\n';}
    }else{Fenwick t({2,1,3,4,5});cout<<t.sum(1,4)<<'\n';t.add(2,2);cout<<t.sum(0,5)<<'\n';}
}

import sys

class Fenwick:
    def __init__(self,a):
        self.n=len(a);self.bit=[0]*(self.n+1)
        for i,x in enumerate(a):
            self.add(i,x)

    def add(self,index,delta):
        i=index+1
        while i<=self.n:
            self.bit[i]+=delta;i+=i&-i

    def prefix(self,end):
        result=0;i=end
        while i>0:
            result+=self.bit[i];i-=i&-i
        return result

    def sum(self,left,right):
        return self.prefix(right)-self.prefix(left)

if __name__=='__main__':
    lines=sys.stdin.read().splitlines()
    if lines:
        n,q=map(int,lines[0].split());t=Fenwick(list(map(int,lines[1].split())))
        for line in lines[2:2+q]:
            op,l,r=line.split();l=int(l);r=int(r)
            if op=='A':
                t.add(l,r)
            else:
                print(t.sum(l,r))
    else:
        t=Fenwick([2,1,3,4,5]);print(t.sum(1,4));t.add(2,2);print(t.sum(0,5))

Không nhập dữ liệu, chương trình in 8 rồi 17 như hai truy vấn mô tả. Input riêng có n,q, một dòng n giá trị và q lệnh. A i delta cộng delta vào vị trí i; Q l r hỏi tổng [l,r). n dương, i trong [0,n), 0<=l<=r<=n. Cho phép giá trị và delta âm trong bài tổng này.

Code C++ dùng long long cho các tổng. Mọi tổng lưu ở bit, tổng tiền tố và phép trừ trả đoạn phải vừa kiểu số; cập nhật tích lũy có thể làm miền giá trị lớn hơn input ban đầu. Python có số nguyên lớn, nhưng không thay được việc kiểm chỉ số hoặc giới hạn bộ nhớ.

Các hàm không tự sửa input chỉ số sai. Đặc biệt index=−1 có thể làm vòng cộng bắt đầu ở 0 và không thoát trong cách cài hiện tại. Hợp đồng chỉ số hợp lệ cần được giữ ở phần gọi hoặc kiểm dữ liệu của ứng dụng thật.

Gán điểm khác cộng điểm

Nếu đề muốn đặt a[i] thành value, cần biết giá trị cũ để tính delta=value−old. Có thể giữ thêm mảng a và cập nhật nó, hoặc lấy old bằng sum(i,i+1) rồi gọi add. Gọi add(i,value) trực tiếp sẽ cộng thêm value, không phải gán.

Ví dụ a[2] đang là 3 và muốn gán thành 5, delta=2. Nếu truyền 5 vào add, kết quả thành 8 và mọi tổng chứa vị trí đó đều sai. Đây là lỗi giao tiếp thao tác, không phải lỗi lowbit.

Trong bài đếm tần suất, add(rank,1) có nghĩa thêm một lần xuất hiện. Nếu xóa một phần tử, có thể add(rank,−1) nhưng phải bảo đảm tần suất logic không âm nếu những thao tác sau dựa vào tính chất đếm.

Đếm nghịch thế với Fenwick tần suất

Một cặp i<j là nghịch thế khi a[i]>a[j]. Duyệt từ phải sang trái, Fenwick lưu số lần xuất hiện của các giá trị đã gặp bên phải. Số phần tử nhỏ hơn a[i] là một truy vấn tiền tố trên thứ hạng giá trị; cộng nó vào đáp án rồi thêm a[i] vào cấu trúc.

Nếu giá trị lớn hoặc âm, nén tọa độ thành các hạng từ 0 mà vẫn giữ thứ tự so sánh. Với rank của a[i], prefix(rank) đếm những hạng nhỏ hơn nghiêm ngặt, không gồm các giá trị bằng. prefix(rank+1) sẽ đếm cả bằng và giải một điều kiện khác.

Mảng [2,2,1] có hai nghịch thế, từ mỗi số 2 tới số 1, không có nghịch thế giữa hai số 2. Đây là ca nhỏ tốt để kiểm phần xử lý giá trị trùng. Đáp án tổng có thể tới n(n−1)/2 nên cần kiểu rộng hơn chỉ số mảng trong C++.

Tổng có phép trừ, min thì không

Từ tổng [0,r) và [0,l), ta trừ để có tổng [l,r). Nhưng biết min hai tiền tố không đủ để biết min phần còn lại: phần tử nhỏ nhất có thể nằm hoàn toàn trước l và che mất mọi thông tin trong đoạn cần hỏi.

Vì vậy, không đổi dấu cộng thành min trong code rồi giữ nguyên công thức hiệu tiền tố. Có các biến thể Fenwick min cho điều kiện cập nhật đặc biệt, nhưng chúng không phải cấu trúc tổng quát cho min đoạn với gán tùy ý. Segment Tree cơ bản thường phù hợp hơn với yêu cầu đó.

Tìm phần tử thứ k theo tần suất cũng cần các tổng tiền tố không giảm. Nếu tần suất có số âm, điều kiện đơn điệu mất và kỹ thuật đi trên bit để tìm k không còn có cùng bảo đảm. Quyền cộng delta âm trong bài tổng không có nghĩa mọi ứng dụng chọn thứ hạng vẫn hợp lệ.

Độ phức tạp và cách dựng

Mỗi lần tăng hoặc giảm chỉ số bằng lowbit đi qua O(log n) mức, nên add và prefix đều O(log n); tổng đoạn gọi hai prefix vẫn O(log n). Bộ nhớ n+1 ô là O(n). Code dựng bằng cách add từng phần tử, nên thời gian khởi tạo O(n log n).

Có cách dựng tuyến tính bằng truyền tổng mỗi ô tới nhóm cha một lần, nhưng tệp hiện dùng bản lặp add để giữ nhất quán với thao tác đã học. Không nhận công cụ đang dựng O(n) nếu code vẫn gọi add n lần. Với bài rất lớn hoặc cần so hiệu năng, hãy xét đúng bản cài và đo trong môi trường cụ thể.

Range add + point query có thể dùng Fenwick trên mảng hiệu. Range add + range sum có cách dùng hai cây với công thức trọng số chỉ số. Các biến thể thay ý nghĩa dữ liệu đang lưu; không thêm một vòng for lên đoạn rồi vẫn nói mỗi cập nhật chỉ O(log n).

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

Để tự kiểm tra cây Fenwick trên dữ liệu nhỏ, bạn hãy giữ thêm một mảng thường, thực hiện cộng điểm và quét tổng đoạn trực tiếp để đối chiếu sau từng truy vấn. Nên thử kích thước n = 1, các độ dài không phải lũy thừa của 2, giá trị âm, cập nhật lặp tại cùng một chỉ số, đoạn rỗng và đoạn kết thúc đúng tại n.

Tự thử prefix(0)=0, prefix(n) bằng tổng toàn mảng, sum(i,i+1) bằng phần tử tại i. Cộng một delta rồi trừ đúng delta đó phải khôi phục mọi truy vấn. Những tính chất này giúp tìm lỗi lệch một chỉ số nhanh hơn việc chỉ in mảng bit và đoán.

Luyện ngay trên Big-O Coding

Hai bài cập nhật điểm và tổng luyện lowbit cùng việc chuyển chỉ số. Bài nghịch thế chuyển dữ liệu lưu từ giá trị sang tần suất theo hạng; cần nén tọa độ và chọn đúng tiền tố nhỏ hơn nghiêm ngặt để xử lý số trùng.

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

Nguồn tham khảo

• CP-Algorithms: Fenwick Tree
• USACO Guide: Point Update Range Sum
• C++ reference: numeric_limits