「区间和」问题

区间和

对于数组$nums$，所谓「区间和」，就是求解数组$nums$中区间$[i,j]$的元素和：

$nums[i]+nums[i+1]+\cdots+nums[j]$

使用$O(n)$的空间复杂度来实现$O(1)$时间复杂度的快速计算，来代替逐个累加的$O(n)$暴力计算

分类

• 数组不可变：可用「前缀和」、「树状数组」、「线段树」
  • 一维前缀和
  • 二维前缀和
• 数组可变：「前缀和」不适用
  • 单点修改
  • 区间修改

前缀和

所谓「前缀和」，就是用一个数组$preSum$来记录从$nums[0]$到$nums[i]$之间的元素和，

$preSum[i] = preSum[i-1]+nums[i]$

为了解决数组越界问题，通常多申请一个空间，使得$preSum$下标从1开始。

一维前缀和

LC 303. 区域和检索 - 数组不可变

class NumArray {
    int[] pre_sum;
    public NumArray(int[] nums) {
        // pre_sum[1]开始
        pre_sum = new int[nums.length+1];
        for ( int i = 0; i < nums.length; i++ ) {
            pre_sum[i+1] = pre_sum[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return pre_sum[right+1] - pre_sum[left];
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

二维前缀和

LC 304. 二维区域和检索 - 矩阵不可变

方法一 维护每一行/列的一维前缀和

class NumMatrix {
    // 维护每一行的前缀和
    int[][] pres;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        pres = new int[m][n+1];
        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < n; j++ ) {
                pres[i][j+1] = pres[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for ( int i = row1; i <= row2; i++ ) {
            res += (pres[i][col2+1] - pres[i][col1]);
        }
        return res;
    }
}

• 时间复杂度：$O(mn)$，每次检索区间和：$O(m)$
• 空间复杂度：$O(mn)$

方法二 维护二维前缀和

初始考虑四个单元格:

$preSum[i + 1][j + 1] = preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j] + matrix[i][j];$

class NumMatrix {
    int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        preSum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 下标仍然从1开始
                preSum[i + 1][j + 1] = preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // preSum[row1][col1]被减了两次，最后加上
        return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
    }
}

• 时间复杂度：$O(mn)$，检索区间和：$O(1)$
• 空间复杂度：$O(mn)$

树状数组

如果区间可变/可修改，那么「前缀和」应该就失效了，这时候可以使用「树状数组」、「线段树」，由于「线段树」实现起来比「树状数组」复杂，且多数情况下的问题都可以用「树状数组」实现，所以这里暂且只介绍「树状数组」

模板

// 上来先把三个方法写出来
{
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) 
            ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) 
            tree[i] += u;
    }
}

// 初始化「树状数组」，要默认数组是从 1 开始
{
    for (int i = 0; i < n; i++) 
        add(i + 1, nums[i]);
}

// 使用「树状数组」：
{   
    void update(int i, int val) {
        // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    
    int sumRange(int l, int r) {
        return query(r + 1) - query(l);
    }
}

作者：AC_OIer
链接：https://leetcode.cn/problems/range-sum-query-mutable/solution/guan-yu-ge-lei-qu-jian-he-wen-ti-ru-he-x-41hv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。