What is and why Segment Tree?
Now a slight modification in question , if we can change any particular number in an array at index i then we have to modify whole sum array from that index ”i” to “n” ,so if we have an alternate query of changing and finding range sum it will be giving us O(n*q) time complexity.Now the Segment tree comes to rescue , by using segment tree we can reduce the complexity from O(n*q) to O(q*log(n)) which is a big difference when n is large. Now we get the answer why Segment Tree?
Segment Tree(Divide and Conquer Solution)
Solution for segment tree will be:
1)If the range contains a single element,the element itself will be in that node.
2)Otherwise divide the range into two smaller ranges,each will be half the size of original.
Recursive function will be written as:
Level 1: Construction
I added the code for creating the segment tree:
Level 2: Query
Now we have created the tree .Since query operation is quite complex I’ll explain it by example: Suppose we have to query for f(0,4) ,since we can see that there is no such node which is having this range but we can notice that f(0,4) = f(0,2) + f(3,4) and there are nodes in segment tree containing those two ranges so we can conclude that we have a general expression such that f(x,y) = f(x,z) + f(z + 1,y) .
When querying a segment tree, we select a subset of the nodes with the property that the union of their sets is exactly the interval whose sum we seek. To do so, we start at the root and recurse over nodes whose corresponding intervals have at least one element in common with the query interval. Hence, in our example of f(0,4), we notice that both the left and right subtrees contain elements in the query interval; hence, we recurse on both.The left child of the root serves as a base case(See the figure), since its interval is contained entirely within the query interval; hence it is chosen. At the right child of the root, we notice that its left child has descendants in the query interval(figure), but its right does not; hence we recurse on the former and not the latter. The former is now another base case, and it is chosen and then we return the sum of given range.
Time Complexity:Since it is a binary tree so for query it will be taking O(log n).You can check by yourself.
Now in update you just have to check the index of the number in which interval it exist then choosing that interval recursively till we reach the leaf of the tree and updating that leaf,now while you are recursing back you just have to update the node in which the index is such that l <= index <=r (l and r is the range of the node,index is the value to be updated).Below is the code for updating the tree.
Time Complexity:Since the height of the tree is (log n),so for worst case time complexity for update will be O(log n).