# Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity

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.

• Try implementing Segment Trees with Lazy Propagation for updates. – Sagnik Feb 12 '18 at 4:02
• 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) – sss Feb 12 '18 at 4:16
• Check the answer. I added in the part about space complexity. – Sagnik Feb 12 '18 at 4:33

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.

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.

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)$.