添加具有特定「步驟」的查詢列表中的值

我想知道是否有一種方法可以將數值添加到具有特定「步驟」的[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

添加具有特定「步驟」的查詢列表中的值

回答

相關問題