• 前缀和

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

    前缀和、差分数组 - 图1
    模板一般这么写：

    1. class PrefixSum{
    2.     private:
    3.         vector<int> prefix;
    4.       public:
    5.         PrefixSum(vector<int>& arr){
    6.             prefix.reserve(arr.size());
    7.             //下标从0到n-1
    8.             prefix[0]=arr[0];
    9.             for(int i=1;i<prefix.size();++i){
    10.                  prefix[i]=prefix[i-1]+arr[i];  
    11.             }
    12.         }
    13.         int query(int i, int j){
    14.             //下标从0到n-1
    15.             if(i==0){
    16.                 return prefix[j];
    17.             }
    18.             return prefix[j]-prefix[i-1];
    19.         }
    20. };
    • 差分数组

      「差分数组」和前缀和的策略十分相似，差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

    前缀和、差分数组 - 图2

    1. 生成差分数组

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

      **

    2. 借助diff进行区间修改，将区间修改的时间复杂度将到O(1)。

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

    void rangeIncresement(int i, int j, int value){
     diff[i]+=value;
    if(j+1<diff.size()){
         diff[j+1]-=value;   
    }
}
    1. 根据差分数组重构原数组：
      vector<int> ret(diff.size(),0);
ret[0]=diff[0];
for(int i=1;i<ret.size();++i){
  ret[i]=ret[i-1]+diff[i];   
}
return ret;
      最后，模板为：
      class DiffRange{
 private:
     vector<int> diff;
 public:
     DiffRange(vector<int>& arr){
         diff.reserve(arr.size());
         diff[0]=arr[0];
         for(int i=1;i<arr.size();++i){
             diff[i]=arr[i]-arr[i-1];
         }
     }
     void rangeIncresement(int i, int j, int value){
         diff[i]+=value;
         if(j+1<diff.size()){
             diff[j+1]-=value;   
         }
     }
     vector<int> getResult(){
          vector<int> ret(diff.size(),0);
         ret[0]=diff[0];
         for(int i=1;i<ret.size();++i){
             ret[i]=ret[i-1]+diff[i];   
         }
         return ret;   
     }
};