# Fenwick Tree

Sau khi đau não nhức óc chóng mặt hoa mắt ù tai quằn quại không biết đăng gì cộng với vài request nho nhỏ của khán giả thì mình quyết định viết về một cấu trúc dữ liệu vô dụng với một chút bất ngờ. Fenwick Tree. Gọi nó là vô dụng cũng không đúng lắm vì có vài biến thể dùng BIT sẽ tiện hơn nhưng nhìn chung thì vô dụng thật bởi như mọi người biết (hoặc không biết) thì Segment Tree làm được những gì Fenwick Tree làm được và kể cả không làm được.

Nhưng, như đã nói, cái gì cũng sẽ có thế mạnh riêng, đó là lý do mình cho ra series ngắn gồm 3 phần này. Phần đầu tiên sẽ chủ yếu nhắc lại kiến thức cơ bản về Fenwick Tree và dạng truy vấn tính tổng đoạn cơ bản. Sang phần 2, mình sẽ cùng tìm hiểu đến một thứ khá vô dụng nhưng khùng điên và 2 dạng truy vấn tính tổng đoạn khó hơn. Đến phần cuối cùng mình sẽ nói đến biến thể mà khi dùng Fenwick Tree sẽ tiện hơn Segment Tree.

## Ngây thơ: Static Range Queries

Trước tiên, mình cần nhắc lại kiến thức siêu cơ bản về range queries đó chính là **prefix sum**. Với prefix sum, ta có thể tính tổng giá trị của một đoạn $[l..r]$ bất kì trong một static array (các giá trị của mảng giữ nguyên xuyên suốt quá trình trả lời các truy vấn) bằng cách tính tổng của đoạn $[1..r]$ và đoạn $[1..l-1]$, kết quả sẽ bằng $a[1..r] - a[1..l-1]$. Ví dụ trong hình sau để tính tổng của đoạn $[4..6]$ (màu hồng) ta tính tổng đoạn $[1..6]$ (màu xanh) và đoạn $[1..3]$ (màu vàng):


Sau đó thì ta chỉ việc lấy $prefix[6] - prefix[3] = 20 - 4 = 16$.

Với cách dùng prefix sum thì vấn đề sẽ phát sinh khi ta cần thay đổi một phần tử nào đó của mảng, cụ thể là nếu muốn cập nhật một phần tử $a[p]$ nào đó, ta cần thay đổi giá trị các phần tử của mảng prefix sum trong cả đoạn $[p..n]$, dẫn đến độ phức tạp thời gian là $O(n)$, sẽ không hiệu quả nếu ta cần thực hiện nhiều truy vấn. Do đó, hôm nay chúng ta sẽ tìm hiểu một cấu trúc dữ liệu phức tạp và đỡ ngây thơ hơn…

## Sơ lược về Fenwick Tree

### Nguồn gốc

**Fenwick Tree** còn có tên gọi khác là **Binary Indexed Tree (BIT)** (lưu ý BIT khác bit). Người được cho là phát minh ra cấu trúc dữ liệu này là Boris Ryabko, vào năm 1989 [^[1]^](http://boris.ryabko.net/dan1989.pdf). Đến năm 1994, Peter Fenwick giới thiệu lại BIT [^[2]^](https://onlinelibrary.wiley.com/doi/10.1002/spe.4380240306) với một số cải tiến và từ đó BIT được biết đến với cái tên Fenwick Tree.

### Ý tưởng chính

Ý tưởng chính của Fenwick Tree là với một số tự nhiên $k$ bất kì, ta có thể tách nó ra thành tổng của các số có dạng $2^d$ với $d$ là một số tự nhiên, sao cho số lượng các số hạng không vượt quá $\log k$. Điều này cũng dễ hiểu nếu bạn biết lý thuyết của biểu diễn nhị phân.

Lấy số $210$ làm ví dụ, biểu diễn nhị phân (8-bit) của nó là $(11010010)_2$. Ta thấy các vị trí có bit 1 lần lượt là $1$, $4$, $6$, $7$ (xét từ bên phải qua trái và bắt đầu đếm từ $0$). Do đó ta có thể tách 210 thành $2^1 + 2^4 + 2^6 + 2^7 = 2 + 16 + 64 + 128$. Số số hạng không vượt quá $\log k$ là do để biểu diễn $k$ thành số nhị phân ta chỉ cần dùng đến $\log k$ bit đầu tiên.

Tương tự như thế, giả sử ta yêu cầu Fenwick Tree tìm tổng của một đoạn có độ dài là $210$, nó sẽ chia đoạn này thành $4$ đoạn, độ dài mỗi đoạn lần lượt là $2$, $16$, $64$, và $128$.

Bây giờ, thử tách prefix sum theo kiểu này:


Ta thấy có rất nhiều đoạn được tính đi tính lại trong mảng prefix sum. Cụ thể, đoạn $[1..4]$ đã được phần tử thứ $4$ quản lý, nhưng lại còn được quản lý bởi phần tử $5$, $6$, và $7$. Với $n$ càng lớn, số lần lặp lại của các đoạn này càng tăng lên.

Để ý rằng với mỗi phần tử của prefix sum đã được tách như thế này, chỉ có block cuối cùng của nó là “hữu ích”, ta sẽ tận dụng nhận xét này để cải tiến và tạo ra BIT.

## Cập nhật phần tử & Truy vấn đoạn – Sum queries

### Problem

Cho 1 mảng $a$ có $n$ phần tử. Yêu cầu xử lý $q$ truy vấn thuộc 1 trong 2 dạng:

- $1$ $k$ $val$: tăng $a[k]$ lên $val$ đơn vị.
- $2$ $l$ $r$: tính tổng $a[l] + a[l + 1] + ... + a[r - 1] + a[r]$.

Constraints:
- $1 \leq n, q \leq 10^5$.
- $-10^9 \leq a[i] \leq 10^9$.

### Xây dựng Fenwick Tree

Cái tên của cấu trúc dữ liệu này nghe có vẻ “cây” và “nút” và “cạnh” lắm, nhưng tương tự Segment Tree, nó không hề đặt nặng trees theory, các giá trị sẽ được lưu vào mảng.

Với ý tưởng nêu trên, ta sẽ xây dựng Fenwick Tree sao cho nút thứ $i$ của nó quản lý một đoạn $[i - p(i) + 1..i]$ của mảng, nói cách khác là đoạn kết thúc tại $i$ có độ dài $p(i)$. Hàm $p(i)$ ở đây sẽ tách bit 1 nhỏ nhất của $i$. Ví dụ $p(184) = p(10111000_2) = 8$ do trong biểu diễn nhị phân của nó, bit 1 đầu tiên xuất hiện ở vị trí số $3$ (mà $23 = 8$).

Trong phần này, ta đang tìm hiểu về truy vấn tổng nên mỗi nút của cây sẽ chứa tổng của đoạn mà nó quản lý. Hình dưới đây sẽ minh họa vùng quản lý của mỗi nút trong Fenwick Tree với $n = 8$.


Ở hình này, các ô vuông biểu diễn các phần tử của mảng, còn các hình chữ nhật màu xám biểu diễn các nút của BIT. Nút thứ $4$ quản lý đoạn $[1..4]$ do $p(4) = p(100_2) = 4$. Tương tự, nút thứ $6$ quản lý đoạn $[5..6]$ do $p(6) = p(110_2) = 2$.

### Tính tổng đoạn tiền tố

Với cách xây dựng này, ta có thể tính tổng bất kỳ đoạn $[1..k]$ nào bằng cách tính tổng của không quá $\log k$ đoạn con của nó.

Ví dụ với đoạn $[1..7]$, có độ dài bằng $7$, ta tách nó ra thành $3$ đoạn có độ dài lần lượt là $1$, $2$, và $4$ (theo phân tích ban nãy). Ba đoạn này sẽ tương ứng với nút thứ $7$, $6$, và $4$ của Fenwick Tree sau:


Thay vì để chỉ số của các nút thì mình để tổng của đoạn mà nó quản lý (cho một mảng ngẫu nhiên) nhé.

Vậy làm sao để biết là phải chọn nút nào của cây? Ta sẽ xử lý từng bit 1 của $k$ từ nhỏ đến lớn. Trở lại với ví dụ $k = 7$, biểu diễn nhị phân của nó là $(111)_2$. Bắt đầu từ nút số $7$, ta cộng giá trị của nút này vào đáp án (đáp án bằng $12$), khi đó, ta đã xử lý được $p(7) = 1$ phần tử. Đoạn còn lại chưa được xử lý có độ dài $(110)_2 = (6)_{10}$. Ta lại cộng giá trị của nút số $6$ của cây vào đáp án (đáp án bằng $28$), như vậy thêm $p(6) = 2$ phần tử nữa được xử lý. Phần còn lại có độ dài là $(100)_2 = (4)_{10}$, cộng giá trị nút số $4$ vào đáp án (đáp án bằng $100$). Lúc này ta đã xử lý đủ $1 + 2 + 4 = 7$ phần tử của đoạn $[1..7]$ nên dừng lại và đưa ra kết quả.

Một ví dụ khác, để tính tổng đoạn tiền tố có độ dài $(3)_{10} = $(011)2$, ta lấy tổng giá trị các nút tại các vị trí $(011)_2 = (3)_{10}$ và $(010)_2 = (2)_{10}$.

### Tính tổng đoạn

Một khi đã tính được tổng đoạn tiền tố trong $O(\log n)$ thì ta có thể tính tổng một đoạn $[l..r]$ bất kỳ bằng cách kết hợp phương pháp ngây thơ prefix sum và Fenwick Tree. Thực hiện thao tác nêu trên 2 lần cho đoạn $[1..r]$ và $[1..l-1]$ là xong.

### Cập nhật phần tử

Với prefix sum, mỗi lần cập nhật phần tử, ta cần cập nhật tất cả các đoạn đang quản lý nó. BIT cũng thực hiện điều tương tự, nhưng mỗi phần tử sẽ có ít nút quản lý nó hơn. Cụ thể, mỗi phần tử bất kì của mảng được quản lý bởi không quá một nút có độ dài $1$, một nút có độ dài $2$, một nút có độ dài $4$,... một nút có độ dài $2^d$ (với mọi $d$ là số tự nhiên và $2^d$ không vượt quá $n$). Do đó, để cập nhật 1 phần tử nào đó, không quá $\log n$ nút của cây sẽ bị ảnh hưởng, dẫn đến độ phức tạp thời gian là $O(\log n)$.

Ví dụ nếu muốn cập nhật phần tử thứ $3$ thì các nút sau sẽ được cập nhật:


Một điều khá thú vị trong các nút màu hồng là $2$ nút liên tiếp cách nhau một khoảng bằng đúng giá trị $p(i)$ của nút bé hơn, cụ thể, $3 + p(3) = 4$ và $4 + p(4) = 8$.

### Cài đặt

Sau khi tìm hiểu một hồi về Fenwick Tree thì ta vẫn còn 1 vấn đề phát sinh: Làm cách nào để tính hàm $p(k)$ hiệu quả? Bitmask. Tận dụng tính chất `~x = -x-1`, có thể tính $p(k)$ trong $O(1)$ bằng công thức: `p(k) = k & -k`. Với `&` là ký hiệu của bitwise AND [^[3]^](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Và sau đây là code mẫu cho Fenwick Tree cơ bản:

struct fenwick_tree {
    vector<ll> tr;
    fenwick_tree (int n) : tr(n + 1, 0) {}

    int p (int k) {
        return k & -k;
    }

    void add (int k, ll val) {
        if (k >= tr.size()) return;
        tr[k] += val;
        add(k + p(k), val);
        return;
    }

    ll query (int k) {
        if (!k) return 0;
        return query(k - p(k)) + tr[k];
    }
};

Trước đó mình đã có lệnh `typedef long long ll` cho ngắn. Ở hàm `add` và `query`, có thể xài vòng lặp `for`/`while` nhưng mình muốn code ngắn nên dùng đệ quy.

Khi khởi tạo BIT, ta sẽ tạo ra một `vector` có $n + 1$ phần tử, tất cả đều có giá trị bằng $0$ và gọi hàm `add` $n$ lần để gắn các giá trị của mảng $a$ (theo như đề bài) vào cây.

## Index compression

### Problem

Cho 1 danh sách rỗng. Yêu cầu xử lý $q$ truy vấn (1 ≤ q ≤ 105) thuộc 1 trong 3 dạng:

- $1$ $val$: thêm giá trị $val$ vào danh sách.
- $2$ $val$: xóa giá trị $val$ khỏi danh sách (nếu có nhiều giá trị $val$ cùng xuất hiện trong danh sách thì chỉ xóa $1$ lần).
- $3$ $l$ $r$: đếm số lượng phần tử của danh sách sao cho giá trị của nó nằm trong đoạn $[l..r]$.

Constraints:
- $1 \leq q \leq 10^5$.
- $1 \leq val, l, r \leq 10^9$.

### Ý tưởng thuật toán

Dạng này có nhiều cách giải, nhưng hôm nay mình sẽ tập trung vào thuật toán sử dụng frequency table và range queries. Với cách này, một vấn đề phát sinh đó là ta sẽ cần sử dụng đến $10^9$ phần tử cho frequency table nếu cài đặt bình thường. Do đó, ta cần làm một theo tác “nén” các chỉ số lại, từ một nhận xét đó là ta chỉ sử dụng không quá $q$ phần tử của mảng thống kê.

Khi đó, mỗi giá trị phân biệt ở các truy vấn (cả 3 loại) sẽ mang cho mình một “key” phân biệt. Gọi $c(x)$ là key của $x$, ta phải đảm bảo rằng nếu $x < y$ thì $c(x) < c(y)$. Để làm điều này, ta cho hết các giá trị $val$, $l$, và $r$ của tất cả các truy vấn vào một `std::map`, rồi gán cho mỗi giá trị một key như sau:

int n;
map<int,int> c;

void compress() {
    int mark = 0;
    for (auto x : c) c[x.first] = mark++;
    n = c.size();
    return;
}

Khi đó, để đếm xem có bao nhiêu giá trị $x$, ta truy cập vào phần tử thứ $c(x)$ của mảng thống kê. Việc còn lại là xử lý cập nhật phần tử và truy vấn đoạn trên mảng thống kê, sử dụng Fenwick Tree để quản lý mảng này là xong.

## Cập nhật phần tử & Truy vấn đoạn – Min/max queries

Lúc đầu nhiều người thường chê Fenwick Tree cùi bắp hơn Segment Tree do nó không thực hiện được truy vấn tìm phần tử lớn nhất (hoặc nhỏ nhất) trong đoạn $[l..r]$ bất kỳ như Segment Tree. Tuy nhiên, vào năm $2015$, hai nhà nghiên cứu Mircea Dima và Rodica Ceterchi đã khám phá ra một phương pháp hiệu quả để làm điều này sử dụng $2$ BITs [^[4]^](https://www.researchgate.net/publication/282222122_Efficient_Range_Minimum_Queries_using_Binary_Indexed_Trees).

### Problem

Cho mảng $a$ có $n$ phần tử. Yêu cầu xử lý $q$ truy vấn thuộc $1$ trong $2$ dạng:

- $1$ $k$ $val$: gán $a_k = val$.
- $2$ $l$ $r$: tìm giá trị lớn nhất trong đoạn $a[l..r]$.

Constraints:
- $1 \leq n, q \leq 10^5$.
- $-10^9 \leq a_i \leq 10^9$.

### Xây dựng Fenwick Tree thứ 2

Trong thuật toán này, Fenwick Tree thứ nhất, tạm gọi là BIT1, được xây dựng theo cách ở trên, nút thứ $i$ sẽ quản lý một đoạn kết thúc tại i và có độ dài $p(i)$. Tuy nhiên, với BIT2 là “Reversed Fenwick Tree”, nút thứ i sẽ quản lý một đoạn bắt đầu tại $i$ có độ dài $p(i)$. Sau đây là hình minh họa cho BIT2:


Lưu ý, lẻ ra nút thứ $16$ sẽ quản lý đoạn $[16..31]$ nhưng vì $n = 16$ nên nút này chỉ quản lý đoạn $[16..16]$. Cần để ý điều này trong phần cài đặt.

Với Fenwick Tree ngược như thế này, việc thực hiện di chuyển trên các nút của nó ngược với BIT bình thường. Cụ thể là ở phần tìm giá trị nào đó của đoạn, mỗi lần di chuyển giữa các nút thay vì trừ đi $p(k)$, ta sẽ cộng, ở phần cập nhật, thay vì cộng thêm $p(k)$ ta trừ. Lưu ý rằng nếu áp dụng dạng BIT này cho truy vấn tổng ta sẽ tính được tổng của đoạn suffix (hậu tố) thay vì prefix như ta đã tìm hiểu.

### Tìm giá trị lớn nhất trong một đoạn

Vì min queries được thực hiện tương tự, nên ta chỉ sẽ tìm hiểu về max queries.

Ý tưởng của thuật toán là ta sẽ chia đoạn $[l..r]$ cần tìm thành 3 đoạn, đoạn đầu tiên sẽ được BIT2 xử lý, đoạn cuối sẽ được BIT1 xử lý (lưu ý nó hơi ngược lý thuyết), đoạn ở giữa chắc chắn sẽ có độ dài là $1$ và ta chỉ cần tìm phần tử tương ứng của mảng trong $O(1)$ (chứng minh sau).

Ví dụ cho mảng sau, tìm phần tử lớn nhất trong đoạn $[5..13]$:


Trước hết, nhìn bằng mắt thường ta biết được đáp án sẽ là $96$ (vị trí số $6$). Bây giờ ta sẽ cùng tìm hiểu xem cách thuật toán tìm giá trị lớn nhất trong đoạn $[5..13]$ của mảng này như thế nào. Bắt đầu từ nút số $5$ của BIT2, ta sẽ nhảy tới để lấy nhiều giá trị nằm trong đoạn $[5..13]$ nhất có thể:


Trong ảnh này, thay vì để chỉ số của các nút thì mình để giá trị lớn nhất của đoạn mà nó quản lý, ví dụ ở nút thứ $4$ là giá trị lớn nhất trong đoạn $[4..7]$ là $96$.

Ta dừng lại tại vị trí thứ $8$ vì đoạn $[8..15]$ đã tràn ra khỏi đoạn cần tìm. Do đó, giá trị lớn nhất của đoạn đầu tiên là $\max(34, 96) = 96$.

Tương tự, bắt đầu từ vị trí số $13$ của BIT1, nhảy ngược về (giống như cách xử lý Fenwick Tree thông thường) để lấy nhiều giá trị trong đoạn $[5..13]$ nhất có thể:


Ở đây, ta dừng lại ở vị trí số $8$ và lấy $\max(89, 13) = 89$. Do đó đoạn $[5..13]$ sẽ được chia thành $3$ đoạn con như sau:


Vậy đáp án sẽ là $\max(96, 0, 89) = 96$. Nhiệm vụ còn lại là chứng minh nếu thực hiện các phép gán $l = l + p(l)$ và $r = r - p(r)$ một số lần, ta sẽ thu được hai giá trị $l$ và $r$ bằng nhau. Đầu tiên ta cần lưu ý rằng $l \leq r$.

Gọi $s$ là vị trí bit cuối cùng (dò từ trái qua phải) trong biểu diễn nhị phân của $l$ và $r$ sao cho bit thứ $s$ của $l$ khác bit thứ $s$ của $r$. Lấy biểu diễn nhị phân (8-bit) của hai số $21$ và $29$, $(00010101)_2$ và $(00011101)_2$, ta có $s = 3$.

Do các bit từ vị trí $s + 1$ trở đi đã bằng nhau rồi, nên tạm thời ta coi như bỏ qua (cho đỡ rối thì cứ coi như là để bit $0$ hết nhé), việc cần làm là lấy các bit $0, 1,..., s$ của cả hai số và làm cho chúng bằng nhau.

Khi lấy $k$ trừ đi $p(k)$, đơn giản là bit $1$ nhỏ nhất của $k$ sẽ biến thành $0$. Như vậy bằng cách gán $r = r - p(r)$ một số lần, ta có thể biến $r$ thành số $2^s$.

Còn khi ta lấy $k$ cộng thêm cho $p(k)$, $k$ sẽ thay đổi như sau (đoạn này khó giải thích bằng lời nên mọi người xem hình nhé :sob:):



Như vậy, bằng cách gán $l = l + p(l)$ một số lần, ta có thể biến $l$ thành một số có dạng $2^d$ ($d$ là số tự nhiên) sao cho $l \leq 2^d$. Lúc này ta có thể làm sao cho $d = s$ (do $l \leq r$).

Vậy với cách di chuyển trên Fenwick Tree, $l$ và $r$ sẽ gặp nhau tại một điểm.


Sẽ có những trường hợp mà đoạn đầu (màu vàng) và cuối (màu xanh) sẽ chồng lên nhau, dẫn đến việc một số giá trị sẽ bị tính nhiều lần. Tuy nhiên, với tính chất của $\min$/$\max$ hoặc các phép tính tương tự như $\gcd$, $\DeclareMathOperator{\lcm}{lcm} \lcm$,... thì việc này không bị ảnh hưởng, do $\max(a, a) = a$. Và trong những trường hợp ấy, đôi khi nhóm thứ $2$ (màu hồng) sẽ tràn ra khỏi đoạn cần tìm, khi đó ta sẽ không lấy giá trị của nhóm thứ $2$. Ví dụ nếu ta cần tìm đoạn $[9..15]$ thì trường hợp này sẽ xảy ra:


Cuối cùng là về độ hiệu quả, ta đã biết được rằng để tính giá trị của nhóm đầu tiên và cuối cần thực hiện $2$ truy vấn có độ phức tạp $O(\log n)$, nhóm ở giữa (nếu có) chỉ cần tìm trong $O(1)$. Do đó, độ phức tạp thời gian của phần này là $O(\log n)$.

### Cập nhật phần tử

Như phân tích ở phần sum queries, khi cập nhật một phần tử của mảng ta cần cập nhật không quá $\log n$ nút của BIT. Nhưng do đây là max queries, việc cập nhật các nút không đơn giản chỉ là cộng thêm giá trị vào. Gọi $[x..y]$ là đoạn quản lý phần tử cần cập nhật. Gọi vị trí phần tử cần cập nhật là $k$ (ta có $x \leq k \leq y$, nếu không cũng chẳng cần quan tâm đoạn này làm gì) thì giá trị mới của nút sẽ bằng $\max(a[x..k - 1], val, a[k + 1..y])$.

Vậy để cập nhật một phần tử bất kỳ, ta cần cập nhật không quá $2 \times \log n$ nút (do có $2$ BITs), ở mỗi nút ta thực hiện $2$ truy vấn đoạn trong $O(\log n)$. Do đó độ phức tạp thời gian của bước này là $O(\log^2 n)$.

Trong tài liệu, $2$ người nghiên cứu có nêu cách cải tiến phần cập nhật thành $O(\log n)$, nhanh bằng Segment Tree nhưng phần giải thích khá phức tạp.

### Cài đặt

struct fenwick_tree {
    vector<int> bit1, bit2, a;
    int sz;

    fenwick_tree (int n) {
        for (int i = 0; i <= n; i++) {
            a.push_back(INT_MIN);
            bit1.push_back(INT_MIN);
            bit2.push_back(INT_MIN);
        }
        sz = n;
    }

    int p (int k) {
        return k & -k;
    }

    int query (int x, int y) {
        int ans = INT_MIN, l = x, r = y;
        for (; r - p(r) + 1 >= x && r > 0; r -= p(r)) ans = max(ans, bit1[r]);
        for (; l + p(l) - 1 <= y && l > 0; l += p(l)) ans = max(ans, bit2[l]);
        if (r >= x) ans = max(ans, a[r]);
        if (l <= y) ans = max(ans, a[l]);
        return ans;
    }

    void update (int k, int val) {
        a[k] = val;
        for (int x = k; x <= sz; x += p(x)) {
            int m = max(query(max(0, x - p(x)) + 1, k - 1), query(k + 1, x));
            bit1[x] = max(m, val);
        }
        for (int x = k; x > 0; x -= p(x)) {
            int m = max(query(x, k - 1), query(k + 1, min(sz, x + p(x) - 1)));
            bit2[x] = max(m, val);
        }
        return;
    }
};

Ở phần này, mình sử dụng $3$ `vector<int>` cho $2$ BITs và cái còn lại lưu các phần tử gốc của mảng. Trong lúc cài đặt, mọi người lưu ý ở đoạn cập nhật BIT2 vì không phải nút nào của BIT2 cũng quản lý cả đoạn theo như lý thuyết (mình đã giải thích ở trên). Cần xử lý sao cho hàm query luôn gọi giá trị $y$ không vượt quá kích cỡ của mảng.

## Cập nhật đoạn & Tìm phần tử

### Problem

Cho mảng $a$ có $n$ phần tử. Yêu cầu xử lý $q$ truy vấn thuộc $1$ trong $2$ dạng:

- $1$ $l$ $r$ $val$: tăng các phần tử trong đoạn $a[l..r]$ lên $val$ đơn vị.
- $2$ $x$: tính $a_x$.

Constraints:
- $1 \leq n, q \leq 10^5$.
- $-10^9 \leq a_i \leq 10^9$.

### Ý tưởng thuật toán

Để thực hiện yêu cầu cập nhật đoạn và truy vấn tìm $1$ phần tử bất kì, ta tạo ra một **difference array**, mỗi phần tử chứa hiệu của phần tử tương ứng và phần tử trước nó trong mảng, nói cách toán học hơn thì $diff[i] = a[i] - a[i-1]$, riêng $diff[1] = a[1]$.

Khi tăng giá trị của tất cả các phần tử thuộc một đoạn $[l..r]$ cho cùng $1$ giá trị, gọi là $x$, ta để ý rằng hiệu của hai phần tử bất kì thuộc đoạn đó không đổi (cũng giống như tuổi tác, mỗi năm ai cũng tăng lên 1 tuổi nên hiệu tuổi của hai người bất kì sẽ luôn như nguyên), chỉ có $2$ giá trị thay đổi nằm ở biên của đoạn này. Cụ thể, chỉ có hiệu của cặp $(a[l-1], a[l])$ và cặp $(a[r], a[r+1])$ là thay đổi.

Do đó với mỗi truy vấn cập nhật, ta chỉ sẽ phải tăng $diff[l]$ lên $x$ đơn vị và giảm $diff[r+1]$ đi $x$ đơn vị. Với dạng truy vấn còn lại, để tìm giá trị của một phần tử $a[i]$ bất kì, ta chỉ cần tìm tổng của đoạn $diff[1..i]$. Như vậy bài toán này cũng tương tự dạng cập nhật phần tử và truy vấn đoạn nên mình sẽ không cho code mẫu đâu nhé :kissing_heart:

## Cập nhật đoạn & Truy vấn đoạn – Sum queries

### Problem

Cho mảng $a$ có $n$ phần tử. Yêu cầu xử lý $q$ truy vấn thuộc $1$ trong $2$ dạng:

- $1$ $l$ $r$ $val$: tăng các phần tử trong đoạn $a[l..r]$ lên $val$ đơn vị.
- $2$ $l$ $r$: tính tổng đoạn $a[l..r]$.

Constraints:
- $1 \leq n, q \leq 10^5$.
- $-10^9 \leq a_i \leq 10^9$.

Ý tưởng thuật toán

Ở phần trên, ta đã biết được rằng $a_i$ bằng tổng đoạn $diff[1..i]$. Hình dưới đây sẽ cho các bạn thấy mối quan hệ giữa mảng $a$ và mảng diff (ảnh này được tham khảo từ một bài đăng trên VNOI Wiki):


Các ô màu sẽ biểu diễn cho mảng $diff$.

Từ đây, ta có thể tìm ra công thức tính tổng của các đoạn tiền tố của mảng $a$ như sau:

- $a[1..1] = 1 \times diff[1]$
- $a[1..2] = 2 \times diff[1] + 1 \times diff[2]$
- …
- $a[1..i] = i \times diff[1] + (i - 1) \times diff[2] + … + 1 \times diff[i]$

Tuy nhiên, vấn đề phát sinh do sự biến động của hệ số. Để giải quyết điều này, ta để ý rằng tổng của một đoạn $a[1..i]$ bất kì có thể tính bằng $2$ giá trị trung gian. Ví dụ, với đoạn $a[1..5]$ ta có thể tính $2$ giá trị sau:



Khi đó tổng đoạn $a[1..5] = S_1[5] - S_2[5]$. Việc tính $S_2[5]$ vô cùng đơn giản, ta chỉ việc lấy $a[5] \times 3$, tổng quát hơn ta có công thức $S_2[i] = a[i] \times (n - i)$. Ta xây dựng $1$ Fenwick Tree hỗ trợ thao tác cập nhật đoạn & tìm phần tử (chúng ta đã được tìm hiểu), mỗi lần tìm ra được phần tử thì nhân thêm cho $n - i$.

Nhiệm vụ còn lại là tính $S_1$ một cách hiệu quả. Bây giờ ta thử viết công thức tính $S_1$ ra:

- $S_1[1] = n \times diff[1]$
- $S_1[2] = n \times diff[1] + (n - 1) \times diff[2]$
- …
- $S_1[i] = n \times diff[1] + (n - 1) \times diff[2] + … + (n - i + 1) \times diff[i]$

Khác với ban nãy, bây giờ mọi giá trị $diff[i]$ đã có $1$ hệ số cố định đó là $n - i + 1$. Do đó, ta cũng sẽ xây dựng $1$ Fenwick Tree cho $S_1$ quản lý các giá trị của mảng $diff$, nhưng lần này thay vì tăng $diff[l]$ lên $x$ đơn vị và giảm $diff[r+1]$ xuống $x$ đơn vị, ta tăng $diff[l]$ lên $(n - l + 1) \times x$ đơn vị và giảm $diff[r+1]$ xuống $(n - r) \times x$ đơn vị. Nói cách khác, các giá trị tăng/giảm sẽ được nhân với hệ số tương ứng của nó. Để tìm một giá trị bất kì của mảng $S_1$, ta tính tổng đoạn tiền tố một cách bình thường.

### Cài đặt

Để tiện và nhìn đỡ rối, mình sẽ định nghĩa hàm $f(i)$ là hệ số tương ứng của $diff[i]$. Hàm này sẽ được tính theo công thức: $f(i) = n - i + 1$. Và sau đây là code mẫu:

struct fenwick_tree {
private:
    vector<ll> S1, S2;
    int n;

public: fenwick_tree (int sz) : S1(sz + 1), S2(sz + 1) {n = sz;}

private:
    int p (int k) {return k & -k;}
    ll f (int k) {return n - k + 1;}

    void add (vector<ll> &tr, int k, ll val) {
        if (k > n) return;
        tr[k] += val;
        add(tr, k + p(k), val);
        return;
    }

    ll sum (vector<ll> &tr, int k) {
        if (!k) return 0LL;
        return sum(tr, k - p(k)) + tr[k];
    }

    ll pre_sum (int k) {
        return sum(S1, k) - sum(S2, k) * ll(n - k);
    }

public:
    void update (int l, int r, ll val) {
        add(S1, l, f(l) * val);
        add(S1, r+1, - f(r+1) * val);
        add(S2, l, val);
        add(S2, r+1, -val);
        return;
    }

    ll query (int l, int r) {
        return pre_sum(r) - pre_sum(l-1);
    }
};

## Two-dimension Fenwick Tree

Tất cả những gì ta đã tìm hiểu dùng để xử lý range queries cho mảng $1$ chiều, bây giờ ta sẽ tính đến chuyện xử lý cho mảng $2$ chiều. Bài toán cho một ma trận có kích thước $n \times m$ và yêu cầu cập nhật một phần tử hoặc cho biết tổng của một hình chữ nhật con bất kì.

### Xây dựng 2D Fenwick Tree

Với dạng mảng $2$ chiều, ta xây dựng một BIT lớn có độ dài $n$, mỗi nút sẽ quản lý một số dòng. Nút thứ $i$ quản lý các dòng từ dòng thứ $i - p(i) + 1$ đến dòng thứ $i$. Ta sẽ “nén” các dòng đó lại thành $1$ mảng có độ dài $m$ và xây dựng một BIT con để quản lý nó. Ví dụ cho $n = 6$ và $m = 4$, khi đó nút thứ $2$ của BIT lớn sẽ quản lý dòng thứ $1$ và $2$, ta lấy $2$ dòng này, “nén” lại thành một mảng và cho một BIT con quản lý nó.


Tổng quát hơn, với nút nằm tại vị trí $(i, j)$ ($i$ là số thứ tự dòng, $j$ là số thứ tự cột) sẽ quản lý hình chữ nhật con có gốc trên trái là vị trí $(i - p(i) + 1, j - p(j) + 1)$ và gốc dưới phải là vị trí $(i, j)$. Ví dụ, trong ma trận $8 \times 8$, nút ở ô $(6, 4)$ sẽ quản lý các ô sau:


### Tính tổng hình chữ nhật con có gốc trên trái ở vị trí (1, 1)

Để tính tổng của một hình chữ nhật con bất kì có gốc trên trái ở $(1, 1)$ và gốc dưới phải ở $(i, j)$, trước hết ta cần chia hình chữ nhật này ra thành các nhóm theo hàng. Ví dụ, để tính hình chữ nhật con có gốc dưới phải ở ô $(7, 6)$, ta sẽ chia nó ra thành 3 nhóm:

- Nhóm $1$: Từ hàng $1$ đến hàng $4$ (tương ứng BIT thứ $4$ / quản lý các ô màu xanh).
- Nhóm $2$: Từ hàng $5$ đến hàng $6$ (tương ứng BIT thứ $6$ / quản lý các ô màu vàng).
- Nhóm $3$: Hàng $7$ (tương ứng BIT thứ $7$ / quản lý các ô màu hồng).


Với những kiến thức ta đã tìm hiểu, có thể kết luận rằng số lượng nhóm sẽ không vượt quá $\log n$. Tiếp theo, với mỗi nhóm như vậy, ta lại tách ra thành các nhóm theo cột để tính tương tự cách tính prefix sum trên BIT bình thường:


Với mỗi BIT được chọn, ta sẽ tính tổng đoạn $[1..j]$. Ở ví dụ trên, ta đã chọn BIT số $4$, $6$, và $7$.

- Ta dùng BIT số $4$, tính tổng đoạn $[1..6]$. Chính xác hơn thì là hình chữ nhật con có gốc trên trái là $(1, 1)$ và gốc dưới phải là $(4, 6)$.
- Đến BIT số $6$, ta lại làm điều tương tự, tính tổng cho hình chữ nhật con có gốc trên trái là $(5, 1)$ và gốc dưới phải là $(6, 6)$.
- Cuối cùng là tổng đoạn $[1..6]$ trong BIT số $7$, tương ứng hình chữ nhật con có gốc trên trái là $(7, 1)$ và dưới phải là $(7, 6)$.
- Sau khi tính xong hết thì ta lấy $3$ giá trị này cộng lại.

Ta nhận thấy với mỗi BIT được chọn, ta lại thực hiện một thao tác tính tổng đoạn tiền tố trong $O(\log m)$. Do đó độ hiệu quả của bước này là $O(\log n \times \log m)$.

### Prefix sum 2D
Đối với prefix sum dành cho mảng $1$ chiều, ta sẽ tính $2$ giá trị tổng đoạn tiền tố. Còn đối với mảng $2$ chiều, ta cần tính $4$ giá trị, sau đó tổng của một hình chữ nhật con bất kì của đoạn này sẽ được tính bằng công thức:

$$ \DeclareMathOperator{\sum}{sum} \sum(x, y, u, v) = \sum(1, 1, u, v) - \sum(1, 1, u, y - 1) $$

$$ - \sum(1, 1, x - 1, v) + \sum(1, 1, x - 1, y - 1) $$

Ở đây $\sum(x, y, u, v)$ là tổng của hình chữ nhật con có gốc trên trái là $(x, y)$ và gốc dưới phải là $(u, v)$.

Để dễ hiểu hơn, ta sẽ đặt $4$ điểm $A(u, v)$, $B(x - 1, v)$, $C(u, y - 1)$, và $D(x - 1, y - 1)$. Khi đó để tính đoạn được đánh dấu bằng viền đậm, ta tính tổng của $4$ hình chữ nhật con có gốc trên trái ở vị trí $(1, 1)$ và gốc dưới phải lần lượt là các vị trí $A$, $B$, $C$, $D$. Sau đó có thể tính tổng của đoạn cần tìm bằng công thức $S = A - B - C + D$.


Như vậy với mỗi truy vấn, ta cần gọi hàm tính tổng $4$ lần với độ phức tạp thời gian là $O(\log n \times \log m)$.

Ta còn có một nhận xét là với mảng $d$ chiều, Fenwick Tree sẽ chậm hơn Segment Tree $2^d$ lần nhưng lại tiết kiệm được bộ nhớ $2^d$ lần.

### Cập nhật phần tử

Việc cập nhật phần tử tương tự với thao tác cập nhật trên mảng $1$ chiều, nhưng thay vì chỉ cập nhật $1$ BIT thì ta sẽ thực hiện thao tác này cho không quá $\log n$ BITs. Do đó, độ phức tạp thời gian cũng là $O(\log n \times \log m)$.

### Cài đặt

struct fenwick_tree_2d {
private:
    vector<vector<ll>> tr;
    int n, m;

public:
    fenwick_tree_2d (int sz_n, int sz_m) {
        vector<ll> v (sz_m + 1, 0LL);
        for (int i = 0; i <= sz_n; i++) tr.push_back(v);
        n = sz_n, m = sz_m;
        return;
    }

private:
    int p (int k) {return k & -k;}

    void add (int u, int k, ll val) {
        if (k > m) return;
        tr[u][k] += val;
        add(u, k + p(k), val);
        return;
    }

    ll pre_sum (int u, int k) {
        if (!k) return 0LL;
        return pre_sum(u, k - p(k)) + tr[u][k];
    }

    ll sum (int i, int j) {
        if (!i) return 0LL;
        return sum(i - p(i), j) + pre_sum(i, j);
    }

public:
    void update (int i, int j, ll val) {
        if (i > n) return;
        add(i, j, val);
        update(i + p(i), j, val);
        return;
    }

    ll query (int x, int y, int u, int v) {
        return sum(u, v) - sum(u, y - 1) - sum(x - 1, v) + sum(x - 1, y - 1);
    }
};