一维，数组固定

给定一个整数数组 nums，求出数组从索引 $i$ 到 $j$ $(i \leq j)$ 范围内元素的总和，包含 $i,j$ 两点。

说明:

1. 你可以假设数组不可变。
2. 会多次调用 sumRange 方法。

一开始的想法是用 $N^2$ 的矩阵存储所有结果，这样的复杂度（时间和空间）是 $O(N^2)$ 。

比较好的想法是存储前缀和。

令

$$S_{i} = \sum_{j=0}^{i}a_{j}$$

有

$$\sum_{k=i}^{j}a_{k} = S_{j} - S_{i-1}$$

但是这样在 $i=0$ 的时候有特殊情况，那么我们令

$$S^{'}_{i} = S_{i-1},i>0 \\ S^{'}_{0} = 0$$

得到

$$\sum_{k=i}^{j}a_{k} = S^{'}_{j+1} - S^{'}_{i}$$

class NumArray {
private:
    vector<int> prefixSums;
public:
    NumArray(vector<int>& nums) {
        int N = (int)nums.size();
        if (nums.empty()) return;
        prefixSums = vector<int>(N+1, 0);

        prefixSums[0] = 0;
        prefixSums[1] = nums[0];
        for (int i = 2; i <= N; ++i) {
            prefixSums[i] = prefixSums[i-1] + nums[i-1];
        }
    }

    int sumRange(int i, int j) {
        return prefixSums[j+1] - prefixSums[i];
    }
};

二维，数组固定

link: https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

e.g.

给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

说明:

1. 你可以假设矩阵不可变。
2. 会多次调用 sumRegion 方法。
3. 你可以假设 $row1 \leq row2$ 且 $col1 \leq col2$。

同上考虑前缀和，不过这里考虑的是右下角坐标为 $(i,j)$ 的左上角为 $(0,0)$ 的方块前缀和。记作$B_{i,j}$. 根据容斥原理，可以推得给定 $(i, j), (k, l)$ 的方块，使用 $B$ 表示为

$$\text{sum}(i,j,k,l) = B_{k,l} - B_{k, j-1} - B_{i-1, l} + B_{i-1, j-1}$$

同样我们需要处理 0 的特例，所以这里我们令

$$S_{i,j} = B_{i-1, j-1}\forall i>0, j>0 \\ S_{i,0} = 0,\ S_{0,j} = 0$$

得到

$$\text{sum}(i,j,k,l) = S_{k+1,l+1} - S_{k+1, j} - S_{i, l+1} + S_{i, j}$$

而求 $S$ 本身的过程也是一个容斥原理+DP的过程

class NumMatrix {
private: 
    vector<vector<int>> partialSum;
    int M;
    int N;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        M = matrix.size();
        N = matrix[0].size();
        partialSum = vector<vector<int>>(M+1, vector<int>(N+1, 0));

        for (int i = 0; i < M; ++i)
            partialSum[i+1][1] = matrix[i][0] + partialSum[i][1];
        for (int j = 0; j < N; ++j)
            partialSum[1][j+1] = matrix[0][j] + partialSum[1][j];
        for (int i = 1; i < M; ++i)
            for (int j = 1; j < N; ++j)
                partialSum[i+1][j+1] = partialSum[i][j+1] + partialSum[i+1][j] - partialSum[i][j] + matrix[i][j];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return partialSum[row2+1][col2+1] + partialSum[row1][col1] - partialSum[row1][col2+1] - partialSum[row2+1][col1];
    }
};

一维，数组可以修改

给定一个整数数组 nums，求出数组从索引 i 到 j $(i \leq j)$ 范围内元素的总和，包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

link: https://leetcode-cn.com/problems/range-sum-query-mutable/

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

说明:

1. 数组仅可以在 update 函数下进行修改。
2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

直接线段树, 附上拙劣的树实现

struct SegmentTreeNode {
    SegmentTreeNode *left;
    SegmentTreeNode *right;
    int leftBd, rightBd;
    int val;
    SegmentTreeNode() : left(nullptr), right(nullptr), val(0), leftBd(0), rightBd(0) {}
    ~SegmentTreeNode() {
        if (left) delete left;
        if (right) delete right;
    }
    bool isLeaf() {return leftBd == rightBd;}
    void update() {val = left->val + right->val;}
};

class SegmentTree {
private:
    SegmentTreeNode * root;
    SegmentTreeNode * buildNode(const vector<int>& nums, int left, int right) {
        if (left == right) {
            SegmentTreeNode *leaf = new SegmentTreeNode();
            leaf->val = nums[left];
            leaf->leftBd = left;
            leaf->rightBd = right;
            return leaf;
        }
        int mid = (left + right) / 2;
        SegmentTreeNode *node = new SegmentTreeNode();
        node->leftBd = left;
        node->rightBd = right;
        node->left = buildNode(nums, left, mid);
        node->right = buildNode(nums, mid + 1, right);
        node->val = node->left->val + node->right->val;
        return node;
    }
    void update_core(SegmentTreeNode *node, int i, int val) {
        if (node->isLeaf()) {
            if (node->leftBd == i) 
                node->val = val;
            return;
        }
        int mid = (node->leftBd + node->rightBd) / 2;
        if (i <= mid) update_core(node->left, i, val);
        else update_core(node->right, i, val);
        node->update();
    }
    int sumRange_core(SegmentTreeNode *node, int i, int j) {
        if (j < node->leftBd || i > node->rightBd) return 0;
        if (i <= node->leftBd && j >= node->rightBd) return node->val;
        return sumRange_core(node->left, i, j) + sumRange_core(node->right, i, j);
    }
public:
    SegmentTree() = default;
    SegmentTree(vector<int>& nums) {
        if (nums.empty()) root = nullptr;
        else root = buildNode(nums, 0, (int)nums.size() - 1);
    }
    ~SegmentTree() {delete root;}

    void update(int i, int val) {
        update_core(root, i, val);
    }

    int sumRange(int i, int j) {
        return sumRange_core(root, i, j);
    }
};

class NumArray {
private:
    SegmentTree segmentTree;
public:
    NumArray(vector<int>& nums) : segmentTree(SegmentTree(nums)) {
    }

    void update(int i, int val) {
        segmentTree.update(i, val);
    }

    int sumRange(int i, int j) {
        return segmentTree.sumRange(i, j);   
    }
};