添加具有特定“步骤”的查询列表中的值

我想知道是否有一种方法可以将数值添加到具有特定“步骤”的[x, y]（具有查询列表）的范围内，速度更快比O(queries * (range_length/step))：你应该加上这样的值：对于每个pos = x + k * step，其中k从0变到无穷大，pos <= y,array[pos] += value。添加具有特定“步骤”的查询列表中的值

我想到了在另一个数组添加值，就像这样：

auxarray[x] += value; 
auxarray[y + 1] -= value; 
for (int i = 1; i <= size; ++i) { 
    auxarray[i] += auxarray[i - 1]; 
    array[i] += auxarray[i]; 
}

不幸的是，我不知道如何处理该值不应该被加入到细胞做。

来源

2016-01-24 mike

不知道我的问题的权利，但如果我这样做，为什么不这样做：

curr = x; 
while (curr <= y) { 
    array[curr] += value; 
    curr += step; 
}

关于faster than O(queries * range_length)，我不认为这是可能的，虽然它是acctually：
O（查询*（range_length /步））

来源

2016-01-24 09:25:57

这也是我的方法，但正如我所看到的，它需要大量的时间。查询的数量可以达到100000，数组的长度也是如此。编辑：的确，它是“长度/步长”，但我想知道我是否可以使用其他数组或数据结构。 – mike

添加具有特定“步骤”的查询列表中的值

回答

相关问题