C ++中的范围加法

假设我们有一个大小为n的数组，并用0初始化，并且我们也有一个值k，我们将执行k个更新操作。每个操作将表示为三元组：[startIndex，endIndex，inc]，它用inc递增子数组A [startIndex ... endIndex]的每个元素（包括startIndex和endIndex）。所有k个操作都执行完后，我们必须找到修改后的数组。

因此，如果输入为length = 5，则更新= [[1,3,2]，[2,4,3]，[0,2，-2]]，则输出将为[-2,0 ，3,5,3]

为了解决这个问题，我们将遵循以下步骤-

• 定义大小为n的数组ret

• 对于初始化i：= 0，当i <a的大小时，更新（将i增加1），执行-

• ret [r]：= ret [r]-a [i，2]

• l：= a [i，0]

• r：= a [i，1] + 1

• ret [l]：= ret [l] + a [i，2]

• 如果r <n，则-

• 对于初始化i：= 1，当i <n时，更新（将i增加1），-

• ret [i]：= ret [i] + ret [i-1]

• 返回ret

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto< v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int< getModifiedArray(int n, vector& a) {
      vector<int< ret(n);
      for (int i = 0; i < a.size(); i++) {
         int l = a[i][0];
         int r = a[i][1] + 1;
         ret[l] += a[i][2];
         if (r < n) {
            ret[r] -= a[i][2];
         }
      }
      for (int i = 1; i < n; i++) {
         ret[i] += ret[i - 1];
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int<> v = {{1,3,2},{2,4,3},{0,2,-2}};
   print_vector(ob.getModifiedArray(5,v));
}

输入值

5, {{1,3,2},{2,4,3},{0,2,-2}}

输出结果

[-2, 0, 3, 5, 3, ]