I need an array-like data structure that stores integers and supports fast addition to multiple evenly spaced elements on given interval. Formally, if $n$ is length of the array, it has to support following operation: given integers $v,s,k,d$ such that $0\leq s$ and $s+d(k-1)<n$, add $v$ to element with index $s+di$ for every nonnegative $i$ less than $k$ and it should do it in at most $O(\log n)$ time (or faster). After doing many of these operations, it should be able to iterate through whole array in $O(n\log n)$ time or faster. It doesn't have to be able to get arbitrary element, just to iterate through all of them once.

I am wondering, whether it is even possible to create such a structure. If it is possible, I don't need whole explanation how to accomplish it, just some rough description of the main idea. If it is not possible, I would love to know why and how could be that proven.

I thought that it could be done by somehow using multiple arrays of different lengths and periodically iterating through them but that would be too slow when using array of every possible length. Another idea that came to my mind was to use only arrays with prime length but it doesn't seem to work either.

If such structure is not possible to create, then assume that $v\in\{-1,1\}$.

  • $\begingroup$ Is the value of $d$ fixed upon the intialization of the data structure or will it change everytime the update operation is performed? $\endgroup$
    – Russel
    Commented May 27 at 8:03
  • $\begingroup$ @greybeard yes, it should be $v$, thanks for noticing, I edited it accordingly. $\endgroup$
    – Risodu
    Commented May 27 at 9:14
  • $\begingroup$ @Russel $d$ is different with each operation. $\endgroup$
    – Risodu
    Commented May 27 at 9:14
  • $\begingroup$ Would you be interested in an algorithm with $O(\sqrt{n})$ updates and $O(n^{1.5})$ time iteration at the end? i.e., replace $\log n$ with $\sqrt{n}$? I don't know whether that is possible, but it "smells" like it might be. $\endgroup$
    – D.W.
    Commented May 27 at 20:37
  • $\begingroup$ @D.W. I am afraid that it would be too slow but you can try it anyway. $\endgroup$
    – Risodu
    Commented May 29 at 9:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.