I. Giới thiệu chung

Những bài toán xử lý truy vấn trên đoạn luôn luôn là một chủ đề rất thú vị trong các kì thi lập trình, đặc biệt là trong các cuộc thi HSG. Chúng ta đã biết đến một cấu trúc dữ liệu là Cây phân đoạn (Interval Tree), rất hiệu quả để xử lý các truy vấn đoạn. Tuy nhiên, cấu trúc dữ liệu này có một nhược điểm là cài đặt khá tốn bộ nhớ, và trong một số trường hợp như xử lý update trên đoạn, cần đến thao tác nâng cao hơn là Lazy Propagation thì mới làm được hiệu quả.

Để khắc phục nhược điểm của Cây phân đoạn, chúng ta có một cấu trúc dữ liệu đơn giản hơn nhiều, đó là Cây nhị phân chỉ số (Binary Indexed Tree). Đây là một cấu trúc dữ liệu rất hiệu quả trong các bài toán liên quan tới xử lý truy vấn cập nhật phần tử và tính tổng trên đoạn, đặc biệt lại cài đặt đơn giản hơn Cây phân đoạn, nên rất được yêu thích. Sau đây, chúng ta sẽ cùng tìm hiểu về cấu trúc này.

II. Bài toán cơ sở

Cùng xét một bài toán về truy vấn đoạn như sau:

Cho mảng số nguyên $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Bạn cần phải trả lời $Q$ truy vấn thuộc hai loại:

• $1 \ u \ v$: Cộng thêm vào phần tử $a_u$ giá trị $v$.
• $2 \ p$: Tính tổng các phần tử $a_1, a_2, \dots, a_p$.

Yêu cầu: Hãy trả lời các truy vấn loại $2$ và đưa ra kết quả?

Input:

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $Q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$.
• $Q$ dòng tiếp theo, mỗi dòng gồm: Số đầu tiên là $1$ hoặc $2$ thể hiện loại truy vấn, theo sau là hai số $u, v$ hoặc số $p$ thể hiện truy vấn tương ứng.

Ràng buộc:

• $1 \le n \le 10^5$.
• $1 \le Q \le 10^5$.
• $1 \le u \le n; 1 \le v \le 10^4$.
• $1 \le p \le n$.

Subtasks:

• Subtask 1 (50% số điểm): $1 \le n, Q \le 10^3$.
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.

Output:

• Với mỗi truy vấn loại $2,$ in ra kết quả trên một dòng.

Sample Input:

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

Sample Output:

32
24

Lời giải ngây thơ

Trước hết, chúng ta sẽ xem xét cách giải quyết subtask 1 của bài toán này. Có hai cách dễ dàng nhất để giải quyết nó như dưới đây:

Cách 1

Với truy vấn loại $1,$ ta cứ tăng $a_u$ lên $v$ đơn vị với từng truy vấn, còn với truy vấn loại $2$ thì duyệt qua tất cả các phần tử từ $a_1$ tới $a_p$ và tính tổng của chúng.

void update(int u, int v, int n, vector < int > &a)
{
    a[u] += v;
}

int get_sum(int p, vector < int > &a)
{
    // Có thể thay thế bằng vòng lặp từ 1 tới p.
    return accumulate(a.begin() + 1, a.begin() + p + 1, 0);
}

Với cách làm này, ta có độ phức tạp như sau:

• Mỗi thao tác update: $O(1)$.
• Mỗi thao tác truy vấn tổng: $O(p) \approx O(n)$.
• Tổng quát: Có $Q$ truy vấn, nên độ phức tạp là $O(n \times Q)$

Như vậy, cách làm này không thể đáp ứng ràng buộc của bài toán.

Cách 2

Ta sử dụng mảng tổng tiền tố để lưu tổng của các phần tử và truy vấn tổng trong $O(1)$.

Khi cập nhật một phần tử, ta sẽ phải cập nhật lại tất cả các vị trí chứa phần tử đó trên mảng tổng tiền tố thay vì cập nhật trực tiếp vào mảng $a$ ban đầu.

void data_preparation(int n, vector < int > &a, vector < int > &prefix_sum)
{
    prefix_sum[1] = a[1];
    for (int i = 2; i <= n; ++i)
        prefix_sum[i] = prefix_sum[i - 1] + a[i];
}

void update(int u, int v, int n, vector < int > &prefix_sum)
{
    for (int i = u; i <= n; ++i)
        prefix_sum[i] += v;
}

int get_sum(int p, vector < int > &prefix_sum)
{
    return prefix_sum[p];
}

Cách làm này có độ phức tạp như sau:

• Thao tác xây dựng mảng tồng tiền tố: $O(n)$.
• Thao tác cập nhật một vị trí: $O(p) \approx O(n)$.
• Thao tác truy vấn tổng: $O(1)$.
• Tổng quát: Có $Q$ truy vấn tổng cộng, nên độ phức tạp vẫn bị lên tới $O(n \times Q)$.

Có thể thấy, ta cần một cấu trúc dữ liệu có thể hỗ trợ trả về kết quả giống tính chất tổng tiền tố, nhưng vẫn đảm bảo được tốc độ của thao tác cập nhật phải nhanh.

III. Cây nhị phân chỉ số (Binary Indexed Tree)

1. Cải tiến truy vấn cập nhật

Hình vẽ dưới đây minh họa tính chất của mảng tổng tiền tố trên một mảng $A$ gồm $8$ phần tử:

<center>

</center>

Nhận xét thấy, một phần tử $sum[j]$ sẽ chứa phần tử $a_i$ trong tổng nó lưu nếu như $j \ge i,$ vì vậy, mỗi khi một phần tử $a_i$ được cập nhật, thì ta cần cập nhật lại tất cả các $sum[j]$ chứa nó, tức là $j - i + 1$ phần tử cần được cập nhật. Số lượng này gần tương đương với độ dài của mảng, dẫn đến thao tác cập nhật bị mất thời gian.

Để tăng tốc độ cập nhật phần tử, cần bố trí lại phạm vi của từng đoạn gắn với $sum[j]$ để cực tiểu số phần tử sum cần cập nhật nhưng vẫn phải đảm bảo tính liên tục để áp dụng tính chất của prefix sum.

2. Tính chất lũy thừa cơ số 2

Tính chất: Mỗi số nguyên dương $n$ đều có thể được biểu diễn dưới dạng tổng của các lũy thừa cơ số $2$ (do biểu diễn nhị phân). Ví dụ như $10 = 2^3 + 2^1, 20 = 2^4 + 2^2, \dots$

Dựa vào tính chất trên, ta có thể phát triển một ý tưởng: Để tính tổng các phần tử thuộc đoạn $[1, n],$ ta sẽ tách đoạn này thành các đoạn nhỏ hơn có độ dài $2^k$ và cộng tất cả các tổng tính được trên từng đoạn vào với nhau.

Cụ thể, đặt $n=2^{i_1}+2^{i_2}+ \cdots +2^{i_k} \ (i_1 > i_2 > \cdots >i_k \ge 0)$. Để tính tổng đoạn $[1...n],$ ta tính tổng các phần tử thuộc đoạn $[1;2^{i_1}],$ sau đó tính tiếp tổng của đoạn $[2^{i_1}+1; 2^{i_1}+2^{i_2}],...$ lặp lại quá trình này cho đến khi ta đến đoạn cuối cùng là $[2^{i_1}+2^{i_2}+ \cdots +2^{i_k−1}+1; n]$. Vì $n$ có thể có tối đa $\log_2 n$ bits, vì thế độ phức tạp khi tính tổng theo cách này là $O(C. \log n),$ trong đó $O(C)$ là độ phức tạp khi lấy tổng một đoạn.

<center>

Minh họa cách chia đoạn đối với các giá trị $n = [1...8]$

</center>

Quan sát hình vẽ minh họa trên, ta nhận thấy rằng: Độ dài của đoạn cuối cùng khi chia đoạn đối với mỗi giá trị $n$ sẽ bằng với giá trị của bit nhỏ nhất (bit trái nhất) trong biểu diễn nhị phân của $n$ ($4 = 100 \to$ độ dài đoạn cuối cùng là $2^2 = 4,...$). Cây nhị phân chỉ số được xây dựng dựa trên nhận định này: Ta sẽ lưu thông tin về block cuối cùng của từng chỉ số $i \ (1 \le i \le n)$ và thực hiện truy vấn dựa vào đó.

<center>

Minh họa cây BIT với mảng $A$ gồm $8$ phần tử

</center>

Trong hình trên, những đoạn được tô đậm là đoạn của phần tử chỉ số $i$ được BIT lưu trữ; những đoạn được tô nét mảnh không được lưu trữ trực tiếp mà sẽ được truy cập gián tiếp.

3. Cài đặt BIT

Nhờ vào tính chất đã nói ở trên, ta có thể cài đặt Cây nhị phân chỉ số dưới dạng một mảng có độ dài đúng bằng độ dài mảng mà ta đang làm việc.

vector < int > bit(n + 1);

Cây nhị phân chỉ số hỗ trợ tốt nhất đối với các thao tác tìm tổng, tìm max và min (từ đầu dãy số tới một vị trí) và cập nhật (một phần tử hoặc một đoạn). Sau đây chúng ta sẽ cài đặt minh họa thao tác tìm tổng để giải quyết bài toán đã đặt ra, các thao tác khác sẽ cài đặt dựa trên ý tưởng tương tự.

Thao tác tìm tổng

Để tìm tổng các phần tử trong đoạn $[1...p],$ ta sẽ lần lượt đi qua tất cả bit của $p$ theo giá trị tăng dần (từ phải qua trái trong biểu diễn nhị phân). Mỗi lần đi qua $p,$ ta sẽ cộng $bit[p]$ vào kết quả hiện tại, rồi trừ đi giá trị của bit nhỏ nhất của $p$ khỏi chính nó; quá trình lặp lại cho đến khi $p=0$.

Rất may mắn, ta lại có một công thức để lấy bit nhỏ nhất của số $p$ là $p \text{ AND } \big( \text{NOT } (p - 1)\big),$ mà được biểu diễn trong C++ là p & ~(p - 1). Trong C++, khi thao tác bit với số âm, chương trình biên dịch sử dụng phép bù $2$: ~p = - p - 1; vì vậy ta có phép biến đổi: p & ~(p - 1) $=$ p & (-(p - 1) - 1) $=$ p & (-p) dễ sử dụng hơn. Như vậy, mỗi bước biến đổi ta sẽ dùng lệnh: p -= (p & (-p)).

int get_sum(int p, vector < int > &bit)
{
    int id = p, sum = 0;
    while (id > 0)
    {
        sum += bit[id];
        id -= (id & (-id));
    }
	
    return sum;
}

Độ phức tạp: $O(\log_2 n ),$ do $n$ có tối đa $\log_2 n$ bits.

Thao tác cập nhật

Để cập nhật phần tử tại vị trí $u,$ ta sẽ thực hiện quá trình ngược lại so với khi truy vấn tìm tổng: cộng giá trị bit nhỏ nhất của $u$ vào chính nó cho đến khi $u$ vượt ngoài biên của mảng.

void update(int u, int v, int n, vector < int > &bit) 
{
    int id = u;
    while (id <= n) 
    {
        bit[id] += v;
        id += (id & (-id));
    }
}

Thuật toán trên sẽ chạy chính xác, bởi vì: Mỗi khi ta cộng thêm một lượng bằng với $2^k$ ($k$ là bit nhỏ nhất của $u$) thì đoạn dịch qua phải một lượng $2^k$ thành $[l+2^k, r+2^k]$ (do bit nhỏ nhất lúc này vẫn có thể tính là $2^k$). Đồng thời lúc đó, bit nhỏ nhất tăng ít nhất $2$ lần do $2^k$ (mới cộng thêm) $+2^k$ (có sẵn trong $u$) tạo thành $2^{k+1}$ làm cho biên trái dịch trái ít nhất $2^k$ lần thành $[l,r+2^k]$ (nếu có sẵn $2^{k+1}$ trong $u$ thì tiếp tục gộp lại làm bit nhỏ nhất tăng lên là $2^{k+2},...$) do đó biên trái luôn được giữ không vượt quá biên $l$ ban đầu.

Mỗi lần cộng thêm, bit cuối luôn bị dịch lên ít nhất $1$ lần, dẫn đến có tối đa $\log n$ lần dịch bit. Vì thế độ phức tạp khi cập nhật là $O(\log n)$.

4. Cập nhật đoạn với BIT

Sẽ thế nào nếu như bài toán ban đầu được thay đổi như sau: Có $Q$ truy vấn thuộc ba loại cần trả lời:

• $1 \ v \ l \ r$: Cộng thêm $v$ vào tất cả các phần tử $a_l, a_{l + 1}, \dots, a_r$.
• $2 \ u$: Tìm giá trị hiện tại của $a_u$.
• $3 \ l \ r$: Tính tổng các phần tử $a_l, a_{l + 1}, \dots, a_r$.

Nếu như sử dụng cách update từng phần tử như bên trên với tất cả các phần tử trong đoạn cần cập nhật, thì độ phức tạp thuật toán sẽ là $O(Q \times n \times \log n),$ tất nhiên quá chậm. Trong trường hợp cần cập nhật đoạn như vậy, ta có thể cài đặt cải tiến trên Cây nhị phân chỉ số để đẩy nhanh tốc độ.

Cập nhật đoạn và truy vấn một phần tử

Ta cài đặt một mảng phụ, gọi là mảng hiệu. Mảng này sẽ lưu hiệu giữa các phần tử liền kề với nhau, xây dựng đơn giản như sau:

$$\begin{cases}diff[i] = a_i; & \text{nếu } i = 1 \\ diff[i] = a_i - a_{i - 1}; & \text{nếu } 2 \le i \le n \end{cases}$$

<center>

</center>

vector < int > diff(n + 1);

diff[1] = a[1];
for (int i = 2; i <= n; ++i)
    diff[i] = a[i] - a[i - 1];

Sau khi xây dựng mảng $diff,$ ta nhận xét thấy:

$$\sum_{j = 1}^i diff[j] = diff[1] + diff[2] + \cdots + diff[i]$$

$$= a_1 + a_2 - a_1 + a_3 - a_2 + \cdots + a_i - a_{i - 1} = a_i$$

Từ tính chất này, khi tính được mảng hiệu, để tính được giá trị của $a_i$ ta chỉ cần lấy tổng của $i$ phần tử $diff$ đầu tiên. Khi này, bài toán của chúng ta thực chất được đưa về tính tổng trên mảng $diff,$ vấn đề hiện tại là thao tác `update()`` cần được xử lí như thế nào?

Quan sát hình vẽ sau đây để thấy cách cập nhật trên một đoạn $[l...r],$ với giá trị $\Delta = 4$ được cộng vào đoạn $[4...7]$:

<center>

</center>

Khi cập nhật, do các phần tử liền kề trong đoạn $[l...r]$ đều được cộng cùng một giá trị $\Delta$ nên hiệu giữa chúng thực chất vẫn không đổi. Khác biệt duy nhất khi cập nhật nằm ở hai biên của đoạn: giữa $(a_{l−1}, a_l)$ và $(a_r,a_{r+1});$ vì thế ta chỉ cần cập nhật điểm tại hai biên trên mảng hiệu và dùng truy vấn lấy tổng để tính giá trị hiện tại của $a_i$.

Cài đặt

void update_point(int u, int v, int n, vector < int > &bit) 
{
    int id = u;
    while (id <= n) 
    {
        bit[id] += v;
        id += (id & (-id));
    }
}

void update_range(int l, int r, int v, int n, vector < int > &bit) 
{
    update_point(l, v, n, bit);
    update_point(r + 1, -v, n, bit);
}

int get_value_point(int u, vector < int > &bit) 
{
    int id = u, ans = 0;
    while (id > 0) {
        ans += bit[id];
        id -= (id & (-id));
    }
	
    return ans;
}

Truy vấn trên đoạn

Quan sát hình vẽ dưới đây, ta sẽ có một cái nhìn tổng quan hơn giữa tổng các phần tử của mảng hiệu $diff$ và mảng $A$. Giá trị của mỗi $a_i$ bằng tổng của các phần tử $diff$ theo từng cột:

<center>

</center>

Vì $a_i = \sum_{j = 1}^i diff[j],$ nên dựa vào hình, ta có thể tính lần lượt tổng các phần tử từ $a_1$ tới $a_i$ như sau:

• $sum[1] = diff[1]$.
• $sum[2] = 2 \times diff[1] + diff[2]$.
• $sum[3] = 3 \times diff[1] + 2 \times diff[2] + diff[3]$.
• $...$
• $sum[i] = i \times diff[1] + (i - 1) \times diff[2] + \cdots + (i - j + 1) \times diff[j] + \cdots + 2 \times diff[i - 1] + diff[i]$.

Cách làm trên có vẻ khá ổn, tuy nhiên với sự thay đổi của hệ số nhân, thì việc truy vấn liên tục sẽ không thuận tiện. Bởi thế, ta sẽ cố định mỗi $diff[i]$ đều nhân với hệ số bằng $n - i + 1,$ khi đó:

• $sum[1] = n \times diff[1] - (n - 1) \times diff[1]$.
• $sum[2] = n \times diff[1] + (n - 1) \times diff[2] - (n - 2) \times \big(diff[1] + diff[2]\big)$.
• $sum[3] = n \times diff[1] + (n - 1) \times diff[2] + (n - 2) \times diff[3] - (n - 3) \times \big(diff[1] + diff[2] + diff[3]\big)$.
• $...$
• $sum[i] = n \times diff[1] + (n - 1) \times diff[2] + \cdots + (n - j + 1) \times diff[j] + \cdots + (n - i + 1) \times diff[i] - (n - 1) \times \big(diff[1] + diff[2] + \cdots + diff[i]\big)$.

Tức là, ta thu được hệ thức:

$$sum[i] = \sum_{j = 1}^{i} (n - j + 1) \times diff[j] - (n - 1) \times \sum_{j - 1}^i diff[j]$$

Cả hai giá trị $diff[j]$ và $(n−j+1) \times diff[j]$ đã được đơn giản hóa, lúc này ta chỉ cần lưu toàn bộ giá trị $(n−j+1) \times diff[j]$ vào mảng $S_1$ và $diff[j]$ vào mảng $S_2$ và dựng mảng cộng dồn trên hai mảng đó.

Thao tác cập nhật trên mảng $S_2$ giống với thao tác cập nhật đã đề cập ở trên, còn ở mảng $S_1$ thì khác biệt duy nhất là việc xử lý nhân hệ số $(n−j+1)$. Tuy vậy, hệ số trên không đổi trong quá trình tính toán với từng phần tử nên ta chỉ cần nhân hệ số này với giá trị cần cập nhật và áp dụng phương thức tương tự như ở cập nhật trên $S_2$.

Cài đặt

/* 
    Các hàm update và sum cần làm việc trên một trong hai BIT riêng biệt.
    Sử dụng vector cho phép truyền BIT vào làm việc trực tiếp dễ dàng hơn.
*/
vector <int> bit1(n + 1), bit2(n + 1);


void update_point(int u, int v, int n, vector <int> &b) 
{
    int id = u;
    while (id <= n) 
    {
        b[id] += v;
        id += (id & (-id));
    }
}

void update_range(int l, int r, int v, int n, 
                  vector < int > &bit1, vector < int > &bit2) 
{
    update_point(l, (n - l + 1) * v, n, bit1);
    update_point(r + 1, -(n - r) * v, n, bit1);
    update_point(l, v, n, bit2);
    update_point(r + 1, -v, n, bit2);
}

int get_sum(vector < int > &b, int u) 
{
    int id = u, ans = 0;
    while (id > 0) 
    {
        ans += b[id];
        id -= (id & (-id));
    }
	
    return ans;
}

int prefix_sum(int u, int n, vector < int > &bit1, vector < int > &bit2) 
{
    return get_sum(bit1, u) - get_sum(bit2, u) * (n - u);
}

int range_sum(int l, int r, vector < int > &bit1, vector < int > &bit2) 
{
    return prefix_sum(r, n, bit1, bit2) - prefix_sum(l - 1, n, bit1, bit2);
}

IV. Interval Tree hay Binary Indexed Tree?

Sau khi tìm hiểu về Binary Indexed Tree, chắc hẳn các bạn sẽ đặt ra câu hỏi, khi nào ta nên sử dụng BIT, còn khi nào nên sử dụng IT? Hai cấu trúc dữ liệu này về cơ bản khá giống nhau, tuy nhiên khả năng hỗ trợ của chúng thì lại khác nhau, chính vì vậy chúng ta không thể mặc định là bài nào cũng có thể dùng được cả hai cấu trúc này.

Cụ thể, Cây phân đoạn sẽ phù hợp với các bài toán cần lưu trữ thông tin của các đoạn trên dãy số, thông tin đó có thể là max, min, ước chung lớn nhất, tổng,...Còn đối với Cây chỉ số nhị phân, ta chỉ có thể dễ dàng cài đặt đối với những bài toán cần lấy prefix sum và cập nhật giá trị, hoặc tìm min - max nhưng phải tính từ đầu dãy số. Chính vì thế, những bài toán nào có thể giải bằng BIT thì đều có thể giải bằng IT, nhưng điều ngược lại thì không. Đây là một khuyết điểm mấu chốt của BIT, vì thế cần nắm rõ tính chất và những bài toán để quyết định có nên sử dụng BIT không.

Các bạn có thể tham khảo bài tập dưới đây để hiểu rõ hơn về việc sử dụng IT hay BIT: Sereja and Brackets. Đây là một bài tập chỉ có thể sử dụng Cây phân đoạn mà không thể sử dụng Cây tìm kiếm nhị phân.

Ngoài ra, các bạn có thể tham khảo series bài tập về BIT trên Hackerrank tại đây.

V. Tài liệu tham khảo

• https://vnoi.info/wiki/algo/data-structures/fenwick.md
• https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/