2
$\begingroup$

I have two operations:

$Sum(i,j)$ : Calculate $A[i]+A[i+1]+....+A[j]$

$Change(i,x)$: Set $A[i]=x$

I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is the length of the input array $A$).

The $Sum(i,j)$ procedure needs to have a runtime complexity of $O(\log(n))$ and the $Change(i,x)$ procedure needs to have a runtime of $O(\log(n))$.

I thought about using a heap seeing as change-key in a heap is $O(\log(n))$, but I cant figure out how exactly to get the $Sum(i,j)$ procedure down to $O(\log(n))$. To me it seems you would need $O(n)$ time to do this. If anyone could nudge me in the right direction I would appreciate it.

$\endgroup$
  • $\begingroup$ Try implementing Segment Trees with Lazy Propagation for updates. $\endgroup$ – Sagnik Feb 12 '18 at 4:02
  • $\begingroup$ Thank you sagnik, this seems to be what i am looking for. I am a little confused about the space complexity of segment trees though. ON wikipedia it is stated that the space complexity is O(nlogn) but elsewhere its says it is O(4n) $\endgroup$ – sss Feb 12 '18 at 4:16
  • $\begingroup$ Check the answer. I added in the part about space complexity. $\endgroup$ – Sagnik Feb 12 '18 at 4:33
1
$\begingroup$

What is a Segment Tree?

It is a data structure which is used to operate over a range of input.

How does it work?

The original elements of the array form the leaves of the tree. Each internal node represents some merging of the sub trees. For example consider the array $A = [1,5,7,8,9,15]$.

If we were to construct a segment tree out of the array with the sum operation in mind, we would have the following tree.segment Tree

What about the run time complexity?

If we try to implement the $Sum(i,j)$ and $Change(i,x)$ operations via a segment tree, the time complexity would be the following:

  • Construction of the Segment Tree: This would take $O(n)$ time.
  • $Sum(i,j)$ : This would take $O(\log(n))$ time.
  • $Change(i,x)$ : This would take $O(\log(n))$ time.

What about the space complexity?

Being an almost complete binary tree, a Segment tree with $n$ leaf nodes will have $2n — 1$ total nodes. Hence the space complexity will be $O(n)$.

$\endgroup$
  • $\begingroup$ I have mentioned Lazy Propagation in my comments to the question. Also note that Lazy Propagation is useful only for range updates. Here the change function only updates one element at a time. Hence lazy propagation is strictly not needed. $\endgroup$ – Sagnik Feb 12 '18 at 5:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.