Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity
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. 



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