如何将数组间隔中的所有值递增给定量

Question

假设我有一个长度为L的数组A.我将给出n个区间(i,j)并且我必须递增A [i]和A [j]之间的所有值.哪个数据结构最适合给定的操作？
间隔是事先已知的.

Answer 1

你可以得到O(N + M).保持一个额外增量数组B与A的相同大小最初为空(填充0).如果你需要用值k增加范围(i,j),那么做B [i] + = k和B [j + 1] - = k

现在在B中进行部分和变换,考虑到你从0开始索引:

for (int i = 1; i < N; ++i) B[i] += B[i - 1];

现在A的最终值是A [i] + B [i]

Answer 2

将所有间隔分成开始和结束索引:s_i,e_i对于开始包括s_i和结束排除的第i个间隔e_i

将所有s_i-s 排序为数组S将所有e_i-s 排序为数组E.

设置increment为零开始输入的线性扫描并在每个循环中添加增量,如果下一个s_i是当前index增量,increment如果下一个e_i是indexdecementincrement

inc=0
s=<PriorityQueue of interval startindexes>
e=<PriorityQueue of interval endindexes>
for(i=0;i<n;i++){
  if( inc == 0 ){
    // skip adding zeros
    i=min(s.peek(),e.peek())
  }
  while( s.peek() == i ) {
    s.pop();
    inc++;
  }
  while( e.peek() == i ) {
    e.pop();
    inc--;
  }
  a[i]+=inc;
}

复杂性(不跳过非增量元素):O(n+m*log(m)) // m是间隔的数量,如果n>>m它是O(n)

跳过元素时的复杂性:O( min( n , \sum length(I_i) ) ),其中length(I_i)=e_i-s_i