Range Sum Query

Range Sum Query Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

思路

• 比较简单的 Range Sum Query，只要知道前缀和就可以计算出不变数组的任意区间的和。

代码

class NumArray {
private:
    vector<int> v_;
public:
    NumArray(vector<int>& nums) {
        v_.push_back(nums[0]);
        for (int num:nums) {
            v_.push_back(v_.back() + num);
        }
        // O(n)
    }

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

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given 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

Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

思路

• 参考之前Range Sum Query 的思想，肯定是要提前计算出需要的数据，最后计算和相当于查表。
• 那么 2D 数组如何计算使用类似的思想呢
• 矩形区域的和相当于多个矩形区域进行叠加后减去重复计算的区域，如下图所示，小矩形区域可以看做三个以左上角（0，0）为顶点的矩形区域与大的矩形区域的操作后的结果

  for a 2D array sum[row+1][col+1]
  sums[i+1][j+1] represents the sum of area from matrix[0][0] to matrix[i][j]
  (notice: we add additional blank row sums[0][col+1]={0} and blank column sums[row+1][0]={0} to remove the edge case checking), so, we can have the following definition
  +-----+-+-------+     +--------+-----+     +-----+---------+     +-----+--------+
  |     | |       |     |        |     |     |     |         |     |     |        |
  |     | |       |     |        |     |     |     |         |     |     |        |
  +-----+-+       |     +--------+     |     |     |         |     +-----+        |
  |     | |       |  =  |              |  +  |     |         |  -  |              |
  +-----+-+       |     |              |     +-----+         |     |              |
  |               |     |              |     |               |     |              |
  |               |     |              |     |               |     |              |
  +---------------+     +--------------+     +---------------+     +--------------+
  
     sums[i][j]      =    sums[i-1][j]    +     sums[i][j-1]    -   sums[i-1][j-1]   +
  
                          matrix[i-1][j-1]

• 因此使用同样的思路计算区域如下

+---------------+   +--------------+   +---------------+   +--------------+   +--------------+
|               |   |         |    |   |   |           |   |         |    |   |   |          |
|   (r1,c1)     |   |         |    |   |   |           |   |         |    |   |   |          |
|   +------+    |   |         |    |   |   |           |   +---------+    |   +---+          |
|   |      |    | = |         |    | - |   |           | - |      (r1,c2) | + |   (r1,c1)    |
|   |      |    |   |         |    |   |   |           |   |              |   |              |
|   +------+    |   +---------+    |   +---+           |   |              |   |              |
|        (r2,c2)|   |       (r2,c2)|   |   (r2,c1)     |   |              |   |              |
+---------------+   +--------------+   +---------------+   +--------------+   +--------------+

代码

class NumMatrix{
private:
    vector<vector<int>> sum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        const int m = matrix.size();
        const int n = m > 0 ? matrix[0].size() : 0;
        sum = vector<vector<int>>(m+1, vector<int>(n+1, 0));
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                sum[i][j] = sum[i-1][j-1] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

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

Range Sum Query Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]
-
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Fenwick Tree (Binary Index Tree)

树状数组，我们需要两个数组来存储，原始数组和 bit 数组

• 假定 i 为左子节点，那么其父节点的坐标为 (i + lowbit(i))
• 假定 i 为右子节点，那么其父节点的坐标为 (i - lowbit(i))
• update(int i, int delta) –> 更新前缀和数组中每一个受影响前缀和，从 i 到 最后一个位置 O (n)
• query(int) –> 直接返回 idx + 1 的前缀和 O(1)
• 求 i 到 j 的前缀和 就可用 query(j+1) - query(i) 来计算
• 求和的基本思想，给定要求和的位置 i，可以用二级制表示法来分段求和，以 13 为例 13 = 2^3 + 2 ^2 + 2 ^ 0;
• 因此 prefixSum(13) = Range(1, 8) + Range(9, 12) + Range(13) // Range(i, j) 表示 i 到 j 的数字求和
• arr = [1, 7, 3, 0, 5, 8, 3, 2, 6, 2, 1, 1, 4, 5]
  prefixSum(13) = RANGE(1, 8) + RANGE(9, 12) + RANGE(13, 13)
  = 29 + 10 + 4 = 43

class FenwickTree{
private:
    vector<int> sum_;
    static inline lowbit(int x) {
        return x & (-x);
    }
public:
    FenwickTree(int n) : sum(n+1, 0) { }
    // 更新一个值，坐标 为 i，需要修改 bit 数组中涵盖了 原始数组 arr[i] 的值 -->  下标 i 以及所有的父节点
    void update(int i, int delta) {
        while (i < sum.size()) {
            sum_[i] += delta;
            i += lowbit(i);
        }
    }
    // 区间求和，假定求 i --> j 的数值之和，可以求 0 --> i-1 , 0 --> j，再相减
    int query(int i) const {
        int sum = 0;
        while (i > 0) {
            sum += sum_[i];
            i -= lowbit(i);
        }
        return sum;
    }
    // 区间求和 和 更新数组 都是 O(logn)
};

class NumArray {
private:
    vector<int> nums_;
    FenwickTree tree_;
public:
    NumArray(vector<int> nums): nums_(move(nums)), tree_(nums.size()) {
        for (int i = 0; i < nums_.size(); i++) {
            tree_.update(i+1, nums[i]);
        }
    }

    void update(int i, int val) {
        tree_.update(i, val - nums[i]);
        nums_[i] -= val;
    }

    int sumQuery(int i, int j) {
        return tree_.query(j+1) - tree_.query(i);
    }
};

Segment Tree

class SegmentNode{
private:
    int start;
    int end;
    int sum;
    SegmentNode *left;
    SegmentNode *right;
public:
    SegmentNode(int start, int end, int sum, SegmentNode *left = nullptr, SegmentNode *right = nullptr):
     start(start), end(end), sum(sum), left(left), right(right);
    SegmentNode(const SegmentNode&) = delete;
    SegmentNode& operator=(const SegmentNode&) = delete;

    ~SegmentNode() {
        delete left;
        delete right;
        left = right = nullptr;
    }
};