# 308. Range Sum Query 2D - Mutable

求二维range sum。求range sum会不断改变值但不会改变总size，用BIT或线段树。BIT返回的是index和Index前所有元素的和，利用presum思想，求\[i, j]之间的就是query(j) - query(i)。又因为是二维，相当于维护M个BIT，每个BIT存的是对应行的presum。

```cpp
class BIT {
public: 
    BIT(const int M, const int N): sums(M, vector<int>(N + 1, 0)) {}

    void update(int i, int j, int delta) {
        while (i < sums.size()) {
            while (j < sums[0].size()) {
                sums[i][j] += delta;
                j += lowbit(j);
            }
            i += lowbit(i); 
        }
    }

    int query(int i, int j) const {
        int sum = 0;
        while (i > 0) {
            while (j > 0) {
                sum += sums[i][j];
                j -= lowbit(j);
            }
            i -= lowbit(i);
        }
        return sum;
    }
    static inline int lowbit(int x) {return x & (-x);}
    vector<vector<int>> sums;
};

class NumMatrix {
public:
    vector<vector<int>> *mat;
    BIT *t;
    NumMatrix(vector<vector<int>> &matrix) {
        const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
        t = new BIT(M, N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                tree.update(i, j, matrix[i][j]);
            }
        }
        mat = &matrix;
    }

    void update(int row, int col, int val) {
        int diff = val - (*mat)[row + 1][col + 1];
        (*t).update(row, col, diff);
    }

    int sumRange(int row1, int col1, int row2, int col2) {
        int res = 0;
        for (int i = row1; i <= row2; ++i) {
            res += (*t).query(i, col2) - (*t).query(i, col1);
        }
        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/315.-count-of-smaller-numbers-after-self/308.-range-sum-query-2d-mutable.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.