# 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)**

**Problem:**We have an array arr{0……….n – 1} and we have to perform two types of queries:

**Structure**

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:

Representation:

**Level 1: Construction**

**In construction of segment tree I’ll give the recursive approach(top down approach), start with root node which leads to a recursive call to it’s two children(see recursive function) which are storing the sum of the range which is half the size of parent node until we reach leaf node which will be storing the original element of an array. And now this recursion will revert back storing sum of it’s child in it’s parent.So,in the parent node we will be having the sum of it’s two child.See the diagram below for more clearity .We will be using an array named as sum[] which will be storing this tree where index “i” stores the sum of parent,it’s child’s sum will be stored at 2*i and 2*i + 1.It will be a full binary tree because we are dividing segment into two parts,so we will be requiring a size of around 2*2^(ceil(log(n))) – 1 to store the binary tree. It is a binary it’s height will be log(n).**

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.**Level 3:Update**

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

Questions for practice:

Easy:

http://www.spoj.com/problems/GSS1/

http://www.spoj.com/problems/KGSS/

http://www.spoj.com/problems/HORRIBLE/

Medium:

http://www.codechef.com/problems/QSET

http://www.codechef.com/problems/FLIPCOIN