### sayan_244's blog

By sayan_244, history, 2 years ago, While learning about segment tree I came across this problem:-

The task is as follows: for a given value x we have to quickly find smallest index i such that the sum of the first i elements of the array a[] is greater or equal to x (assuming that the array a[] only contains non-negative values).

The solution mentions storing prefix sums in the segment trees.

I cannot figure out how to build up a segment tree of prefix sums. Also how is it different from the range sums?  Comments (8)
 » 2 years ago, # | ← Rev. 2 →   No, we don't need to store the prefix sum. We just need to build the simple sum segment tree, it only differs in the way we query the segment tree. Let the required sum be K, idx represent the index of the segment tree and l and r be the array range it covers, then code will look like, int query(int idx, int l, int r, int K){ if( l == r ) return l; int md = (l+r)/2; if( seg[2*idx] >= K ) // left child contains the required index return query(2*idx, l, md, K); else return query(2*idx+1, md+1, r, K-seg[2*idx]); // right segment don't have sum of left segment } /********************************* if( seg < K ){ // answer doesn't exist }else{ ans = query(1, 0, n-1, K); } ********************************/ 
•  » » return query(2*idx+1, md+1, r, K-seg[2*idx]);This is how I understood your code. Supposing the left child doesn't have the sum>=K so we go to right child and look for the K-left child sum. Now if the right child's sum is greater than K-left child sum the l of the right child will be the answer. (since the sum of left child +this right child will end up greater than K)This is how it is?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   Yes, since we know answer do exist (see comments in the code), then if answer is not in the left child then answer will be in the segment covered by right child and hence we call the same function on the right child with sum of the left child removed
•  » » » » Thanks a lot!
•  » » Thanks
 » Do you need to update the elements of the array?If no, use binary search to find the first position. My code (C++)#include #define NMAX 200009 using namespace std; typedef long long ll; ll sum[NMAX], n, x; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> x; for(ll i = 0; i < n; i++){ cin >> sum[i]; if(i > 0) sum[i] += sum[i - 1]; } cout << lower_bound(sum, sum + n , x) - sum; /// Note: elements are numerated from 0 return 0; }  Sample testsInput 1: 5 6 1 2 3 4 5Output 1: 2Input 2: 5 7 1 2 3 4 5Output 2: 3 ~~~~~Otherwise, my solution would be to use a segment tree with range sums. My code(C++)#include #define NMAX 200009 using namespace std; typedef long long ll; struct node{ ll l, r, sum; }segmTree[NMAX * 20]; /// 20 > log2(200009) ll leaves[NMAX], n, v[NMAX]; /// intervals with one element ll parent(ll curNode){ return (curNode-1)/2; /// (2*k+2-1)/2 = (2*k+1-1)/2 = k } ll sibling(ll curNode){ if(curNode % 2 == 0) return curNode - 1; /// is of the form 2*k + 2; its sibling is 2*k+1 else return curNode + 1; } void construct(ll low, ll up, ll currentNode){ /// recursive function that initializes the segment tree segmTree[currentNode] = {low, up, 0}; if(low < up){ construct(low, (low + up) / 2, currentNode * 2 + 1); /// child 1 of node k is 2*k+1 construct( (low + up) / 2 + 1, up, currentNode * 2 + 2); /// child 2 of node k is 2*k+2 } else leaves[low] = currentNode; /// one element } void update(ll currentNode, ll val){ segmTree[currentNode].sum = val; if(currentNode == 0) /// root; has no children return; update(parent(currentNode), val + segmTree[sibling(currentNode)].sum); } ll index(ll targetSum, ll seqLeft){ ll currentNode=leaves[seqLeft]; if(segmTree[currentNode].sum>=targetSum) /// solution return seqLeft; while(currentNode !=0 && segmTree[parent(currentNode)].sum < targetSum) currentNode = parent(currentNode); return index(targetSum - segmTree[currentNode].sum, segmTree[currentNode].r + 1); /// we have added the sum from 'l' to 'r', so we will subtract it from the target sum /// we will search from 'r' + 1 to find the first index } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll queries, queryType, queryParam1, queryParam2; cin>>n>>queries; for(ll i = 1; i <= n; i++) cin>>v[i]; construct(1, n, 0); /// 0 is the root for(ll i = 1; i <= n; i++){ update(leaves[i], v[i]); /// the 'update' function will update range sums } for(ll i=0; i < queries; i++){ cin>>queryType; if(queryType == 1){ cin >> queryParam1 >> queryParam2; /// v[queryParam1] becomes v[queryParam2] update(leaves[queryParam1], queryParam2); } else{ cin >> queryParam1; cout << index(queryParam1, 1) << '\n'; /// the first index of the sum greater or equal to queryParam1 /// the sequence starts from 1 } } return 0; }  Sample testsInput 1: 5 5 1 2 3 4 5 2 6 2 7 1 4 1 2 6 2 8 Output 1: 3 4 3 5 Input 2: 4 1 1 2 3 4 2 11 Output 2: 5 
•  » » Thanks for the detailed implementation. Yes, I was looking for a O(log n) implementation using segment tree.
 » templateint find_prefix_seg(vt & t,int v,int tl,int tr,int x){ if(x>t[v]) return -1; if(tl==tr){ return tl; } int tm=MID(tl,tr); if(t[2*v+1]>=x) return find_prefix_seg(t,v*2+1,tl,tm,x); return find_prefix_seg(t,v*2+2,tm+1,tr,x-t[v*2+1]); }