大家好，又见面了，我是你们的朋友全栈君。
1，前缀和主要适用场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
这里就不写前缀和的代码了，就是用一个数组记录下原有数组的前缀和。比如，prefix[i]就代表着nums[0…i-1]所有元素的累加和，如果我们想求区间nums[i…j]的累加和，只要计算prefix[j + 1] – prefix[i]即可，而不需要遍历整个区间求和。（需要注意的是使用场景是频繁查询某个区间的累加和，而不需要对原始数组进行频繁修改）
2，查分数组的主要适用场景是**频繁对原始数组的某个区间的元素进行增减。**比如说，给定一个数组nums，要求给区间nums[2…6]全部加1，再给nums[3…9]全部减3，再给nums[0…4]全部加2,等等。当然可以使用for循环挨个处理，但是可以利用查分数组来达到O(1)复杂度就可以完成某个动作。diff[i]就是nums[i]和nums[i – 1]之差。比如：
nums： 8 5 9 6 1
diff： 8 -3 4 -3 -5
首先可以通过这个数组来还原原来的数组，也可以利用O(1)复杂度完成给nums[i…j]全部加val的操作。只需两步即可，第一步：diff[i] += val， 这意味着nums[i…]的值全都加val，第二步：diff[j + 1] -= val(j + 1 < size)，这意味着nums[j + 1…]的值全都减val，因为第一步加了。
class Difference{
private:
vector<int> diff;
public:
Difference(vector<int>& nums){
diff.push_back(nums[0]);
for(int i = 1; i < nums.size(); i++){
diff.push_back(nums[i] - nums[i - 1]);
}
}
void increment(int i, int j, int val){
diff[i] += val;
if(j + 1 < diff.size()){
diff[j + 1] -= val;
}
}
vector<int> result(){
vector<int> vec;
vec.push_back(diff[0]);
for(int i = 1; i < diff.size(); i++){
vec.push_back(vec.back() + diff[i]);
}
return vec;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/131828.html原文链接：https://javaforall.net
