How to improve the time complexity of this algorithm?

Question

• n list size
• v[n] list with all values set to 0
• update(k, a) operation which sets v[k] += a
• query(a, b) operation which returns the sum of v[a] + v[a+1] + ... + v[a+b], a<b

These operations give the algorithm a time complexity of O(n * cost of one operation):

---------------------------
| update | query | total  |
---------------------------
|  O(1)  |  O(n) |  O(n)  |
---------------------------

Is there any version of the update and query operations that will improve the total time complexity?

For example I tried to cache every sum between 0 and n in the update operation but I get to an even slower algorithm:

---------------------------
| update | query | total  |
---------------------------
| O(n^2) |  O(1) | O(n^2) |
---------------------------

Any suggestions?

The worst case scenario is of interest to me.

I already know two versions: each with one operation O(1) and the other O(n) or higher.

Answer 1

Thanks to one of the comments by @Niklas B. I've continued my research focusing on Segment Trees.

Representation of Segment trees

• leaf Nodes are the elements of the input array
• each internal node represents some merging of the leaf nodes
• merging is sum of leaves under a node
• an array representation of tree is used to represent Segment Trees
• for each node at index i, the left child is at index 2*i+1, right child at 2*i+2 and the parent is at floor((i-1)/2)

Construction of Segment Tree from given array

• start with a segment arr[0, .., n-1]
• divide the current segment into two halves(if it has not yet become a segment of length 1)
• call the same procedure on both halves, and for each such segment we store the sum in corresponding node
• all levels of the constructed segment tree will be completely filled except the last level.
• the tree will be a Full Binary Tree because we always divide segments in two halves at every level
• since the constructed tree is always full binary tree with n leaves, there will be n-1 internal nodes
• total number of nodes will be 2*n – 1.

Time Complexity

• tree construction has O(n)
• there are total 2n-1 nodes, and value of every node is calculated only once in tree construction
• query has O(Logn)
• to query a sum, we process at most four nodes at every level and number of levels is O(Logn).
• update has also O(Logn)

• to update a leaf value, we process one node at every level and number of levels is O(Logn)

  -------------------------------
  | update  |  query  |  total  |
  -------------------------------
  | O(Logn) | O(Logn) | O(Logn) |
  -------------------------------
  

References:

http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

http://en.wikipedia.org/wiki/Segment_tree

Answer 2

As Niklas notes, this problem is more or less what Fenwick trees were designed for (your queries can be answered as the difference of two prefix sums). I'm writing this answer to point out that it's possible to trade off the operation costs differently.

First, your algorithm with cheap queries can have its update time improved to O(n): compute ahead of time only the prefix sums and use the aforementioned difference trick. Moreover, we can extract the main idea and apply it to any data structure that supports operations

update(k, a, b): for i in a..b, do s[i] += k
query(i): return s[i],

where s now holds the prefix sums instead of the actual values.

Now, classic Fenwick/segment trees have d = 2 children per internal node (are binary). There's nothing stopping us from choosing other values of d. Either update or query has to access a node and its ancestors, and the other has to access the segments comprising the input interval. The former mode of access takes time O(log n / log d). The latter mode takes time O(d (log n / log d)). In this framework, your proposed algorithms in essence take d = n. By taking other values of d, we can account for the precise mix of query/update operations as well as architectural details that may favor flatter tree structures.