前缀和数组

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

若要计算一个数组内区间的和，我们可以定一个for循环，分别计算从i到j之间的取值。这样时间复杂度为O(n)。
我们可以通过建立一个新的数组分别存储当前元素前缀元素和来将时间复杂度降为O(1)。

我们定义一个前缀和数组presum,如果要求区间[i,j]的和。我们只需要计算presum[j+1]-presum[i]即可。

preSum[i] 记录 nums[0..i-1] 的累加和。如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
        sums.push_back(0);
        if (nums.size() > 1){
            for(int i = 1; i < nums.size(); i++){
            sums.push_back(sums[i-1]+nums[i-1]);
        }
        }
    }

    int sumRange(int left, int right) {
        if( left == right) return nums[left];
		else return sums[right]-sums[left]+nums[right];
    }
};

首先构造一个前缀和数组，初始化前缀和数组第一个元素为0，每一个元素都等于前一个元素的前缀和加前一个元素的值。

sumRange函数返回值避免越界，使用sums[right] 而没有使用sums[right+1]

来看Leetcode官方的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
public:
    vector<int> sums;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }

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

将前缀数组长度定义为nums的长度+1，这样在包含上限的计算时可以忽略j+1带来指针越界的问题。

从0开始遍历将当前值相加赋给后继

返回值不需要考虑数组越界问题

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差

1
2
3
4
5
6
7
//构造差分数组
n = nums.size();
vector<int> diff(n);
diff[0] = nums[0];
for( int i = 1; i < nums.size() ; i++ ){
    diff[i] = nums[i] - nums[i-1]; 
}

通过这个 diff 差分数组是可以反推出原始数组 nums 的

1
2
3
for( int i = 1;i<diff.size();i++){
    diff[i] += diff[i-1];
}

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可：

相当于构建了一个新的数组存储的是每个数据项之间的差值，然后只需要修改起始位的差值，即可将后面所有的数值都进行改动，只需要最后还原j+1的改动，即可完成区间的改动操作。时间复杂度为O(1)。