Build tree :- We are builindg here a Tree by using an array,we have taken an dp[] array,if dp[i] denotes parent node then dp[2*i] & dp[2*i+1] will give us its left and right child.For pictorial representation ( https://cp-algorithms.com/data_structures/segment_tree.html )
| 5 | #define ll long long int |
| 6 | //Build tree :- We are builindg here a Tree by using an array,we have taken an dp[] array,if dp[i] denotes parent node then dp[2*i] & dp[2*i+1] will give us its left and right child.For pictorial representation ( https://cp-algorithms.com/data_structures/segment_tree.html ) |
| 7 | void build(ll a[],ll tl,ll tr,ll dp[],ll v) |
| 8 | { |
| 9 | if(tl==tr)dp[v]=a[tl]; |
| 10 | else{ |
| 11 | ll tm=(tl+tr)/2; |
| 12 | build(a,tl,tm,dp,2*v); |
| 13 | build(a,tm+1,tr,dp,2*v+1); |
| 14 | dp[v]=dp[2*v]+dp[2*v+1]; |
| 15 | } |
| 16 | } |
| 17 | //Function to answer queries in logN time,what we are doing here is we are traversing the whole tree and we are going to it's their child then if current range in tree is exist inside the range [l,r],then we will add that value |
| 18 | ll sum(ll v,ll tl,ll tr,ll l,ll r,ll dp[]) |
| 19 | { |