1
$\begingroup$

Let $A[1 . . . n]$ be a given array of $n$ integers, where $n = 2^m$. The following two operations are the only ones to be applied to A:

  • Add(i, y): Increment the value of $A[i]$ by $y$.

  • PartialSum(k): Print the current value of $\sum_{i=1}^{k} A[i].$

One needs to perform these two operations multiple times in any given order. Design a data structure to store A such that each invocation of these two operations can be done in $O(m)$ steps.

What I have designed is the following :

Since the number of elements is $2^n$, $O(m)$ steps implies $O(\log n)$ steps.

We can think of the array as a binary tree represented in array format with the root at $A[0]$ which is the standard notation for a binary tree in array format. I am using an auxiliary array $B[]$ which stores the cumulative sum of elements at each level of the binary tree.

Thus, for an array $A[] = \{1,2,3,4,5\}$ the value of $B$ would be $B[] = \{1,6,15\}$ since in level $0$, we have the element $A[0] = 1$. Similarly, in level 1, we have the elements $A[1]$ and $A[2]$ whose cumulative sum is placed at $B[1] = 6$

Assumption: We have a helper function findlevel(i) which finds the level in the binary tree for a node $i$.

Thus for the Add(i, y) operation, we can perform the $A[i] = A[i] + y$ operation in constant time, and we can call findlevel(i) which would return the value of the level of the node in the binary tree. Once we know the level, we can increment $B[i]$ by $y$ for all $i = level(i)$ to $end$. Thus, it can be carried out in $O(\log n)$ time.

Can the PartialSum(k) operation be computed in $O(\log n)$ time using this data structure?

$\endgroup$
  • $\begingroup$ Hint: Use a binary tree, storing the entries $A[i]$ at the leaves and store in every node the sum of its children. $\endgroup$ – A.Schulz Apr 8 '16 at 6:20
  • 1
    $\begingroup$ @A.Schulz But is it possible to obtain logarithmic time using the data structure I have designed? $\endgroup$ – r.k Apr 8 '16 at 6:30
  • 1
    $\begingroup$ I'm pretty sure this has been asked before (quite a while ago) but I can not find the duplicate. $\endgroup$ – Raphael Apr 8 '16 at 6:54
  • $\begingroup$ @A.Schulz Ain't that will cost a lot of memory. More than it would cost normally. (Not being specific to what is asked in question) $\endgroup$ – Prateek Apr 8 '16 at 14:18
  • 1
    $\begingroup$ @Prateek: No, only twice as much. (A binary tree has roughly as many internal nodes as it has leaves.) $\endgroup$ – A.Schulz Apr 8 '16 at 17:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.