# BIT 2 chiều, range update, range query

:::info
> **Người làm**: Trần Thiên Phúc - 12Ti - K28, THPT Chuyên Hùng Vương, Thành phố Hồ Chí Minh.
> **Nội dung**:
> [TOC]

> Tài liệu tham khảo: [Robert1003 blog](https://robert1003.github.io/2020/01/27/fenwick-tree.html#d-range-update-range-query-1).

> Bài tập áp dụng: [VNOI Wiki](https://wiki.vnoi.info/algo/data-structures/fenwick-2d#b%C3%A0i-t%E1%BA%ADp-%C3%A1p-d%E1%BB%A5ng), [LDQOJ](https://www.lqdoj.edu.vn/problem/dhbb2022table), [VNOJ](https://oj.vnoi.info/problem/hspc14k).

> Bài viết trên VNOJ: [VNOJ](https://oj.vnoi.info/user/TranThienPhuc2657).
:::

---

- Hai truy vấn:
- Update hình chữ nhật góc trái trên là $(x_{1}, \ y_{1})$ tới ô phải dưới là $(x_{2}, \ y_{2})$ cộng $val$
- Tổng hình chữ nhật góc trái trên là $(x_{1}, \ y_{1})$ tới ô phải dưới là $(x_{2}, \ y_{2})$

## Định nghĩa mảng hiệu:
$$d_{i, \ j} = a_{i, \ j} - a_{i - 1, \ j} - a_{i, \ j - 1} + a_{i - 1, \ j - 1}$$
$$\rightarrow a_{i, \ j} = \sum_{k = 1}^{i} \sum_{l = 1}^{j} d_{k, \ l}$$

## Update
- $d_{x_{1}, \ y_{1}} \mathrel{+}= val$
- $d_{x_{2} + 1, \ y_{1}} \mathrel{-}= val$
- $d_{x_{1}, \ y_{2} + 1} \mathrel{-}= val$
- $d_{x_{2} + 1, \ y_{2} + 1} \mathrel{+}= val$

## Query
Định nghĩa $p_{i, \ j}$ là tổng tiền tố từ ô $(1, 1)$ tới ô $(i, j)$
$$p_{i, \ j} = \sum_{k = 1}^{i} \sum_{l = 1}^{j} a_{k, \ l}$$
Như vậy đán án cần trả về là: $p_{i, \ j} - p_{i - 1, \ j} - p_{i, \ j - 1} + p_{i - 1, \ j - 1}$

### Tính $p_{i, \ j}$
$$p_{i, \ j} = \sum_{k = 1}^{i} \sum_{l = 1}^{j} a_{k, \ l}$$
$$= \sum_{k = 1}^{i} \sum_{l = 1}^{j} \sum_{p = 1}^{k} \sum_{q = 1}^{l} d_{p, \ q}$$
Ta nhận thấy: mỗi $d_{p, \ q}$ được cộng lên $1$ lần với $k \geq p$ và $l \geq q$
Cố định $d_{k, \ l}$ ta có số lần được cộng của nó với mỗi $(i, j)$ là $(i - k + 1) \times (j - l + 1)$
$$= \sum_{k = 1}^{i} \sum_{l = 1}^{j} (i - k + 1) \times (j - l + 1) \times d_{k, \ l}$$
Ta nhân phân phối các biến trong ngoặc:
$$= \sum_{k = 1}^{i} \sum_{l = 1}^{j} [(i + 1) - k] \times [(j + 1) - l] \times d_{k, \ l}$$
$$= \sum_{k = 1}^{i} \sum_{l = 1}^{j} [(i + 1) \times (j + 1) \times d_{k, \ l}] - [(i + 1) \times l \times d_{k, \ l}] - [k \times (j + 1) \times d_{k, \ l}] + [k \times l \times d_{k, \ l}]$$
Ở đây ta có thể rời rạc hóa như sau:
$$= \sum_{k = 1}^{i} \sum_{l = 1}^{j} (i + 1) \times (j + 1) \times d_{k, \ l} - \sum_{k = 1}^{i} \sum_{l = 1}^{j} (i + 1) \times l \times d_{k, \ l} - \sum_{k = 1}^{i} \sum_{l = 1}^{j} (j + 1) \times k \times d_{k, \ l} + \sum_{k = 1}^{i} \sum_{l = 1}^{j} k \times l \times d_{k, \ l}$$
Các hằng số $i + 1$ và $j + 1$ không cần bỏ vào trong tổng nên là có thể bỏ ra ngoài:
$$= (i + 1) \times (j + 1) \times \sum_{k = 1}^{i} \sum_{l = 1}^{j} d_{k, \ l} - (i + 1) \times \sum_{k = 1}^{i} \sum_{l = 1}^{j} l \times d_{k, \ l} - (j + 1) \times \sum_{k = 1}^{i} \sum_{l = 1}^{j} k \times d_{k, \ l} + \sum_{k = 1}^{i} \sum_{l = 1}^{j} k \times l \times d_{k, \ l}$$
Bây giờ, ta có thể sử dụng $4$ BIT khác nhau với $4$ cách update khác nhau trên từng BIT và bài toán bây giờ là truy vấn tổng tiền tố bình thường.

## Độ phức tạp
- Update: $\mathcal{O} (\log_{2} n \times \log_{2} m)$
- Query: $\mathcal{O} (\log_{2} n \times \log_{2} m)$

## Code
:::spoiler Code

struct Fenwick_tree {
    ll BIT[N][N][4];

    void update(int x, int y, int val) {
        for (int idx = x; idx <= n; idx += idx & (-idx)) {
            for (int idy = y; idy <= m; idy += idy & (-idy)) {
                BIT[idx][idy][0] += val;
                BIT[idx][idy][1] += 1ll * y * val;
                BIT[idx][idy][2] += 1ll * x * val;
                BIT[idx][idy][3] += 1ll * x * y * val;
            }
        }
    }

    void update(int xl, int yl, int xr, int yr, int val) {
        update(xl, yl, val);
        update(xl, yr + 1, -val);
        update(xr + 1, yl, -val);
        update(xr + 1, yr + 1, val);
    }

    ll get(int x, int y) {
        ll res = 0;
        for (int idx = x; idx > 0; idx -= idx & (-idx)) {
            for (int idy = y; idy > 0; idy -= idy & (-idy)) {
                res += 1ll * (x + 1) * (y + 1) * BIT[idx][idy][0] - 1ll * (x + 1) * BIT[idx][idy][1] - 1ll * (y + 1) * BIT[idx][idy][2] + BIT[idx][idy][3];
            }
        }
        return res;
    }

    ll get(int xl, int yl, int xr, int yr) {
        return get(xr, yr) - get(xl - 1, yr) - get(xr, yl - 1) + get(xl - 1, yl - 1);
    }
};

:::