Help in SPOJ RANGESUM

Can anyone help me to solve this problem by segment tree?

You can do this using simple segment tree.

The idea is this ,just choose an offset,ie lets say the index i in array corresponds to index i+offset in segment tree.

So i’ll say take offset around 10^5,and create the segment tree according to above.(ie index 1 will be 10^5+1 now)

So for 1st query [l,r]=[offset+l,offset+r] in ST.

For 2nd query,update ST[offset]=x,and Offset–

(I took offset 10^5 as in worst case u’ll have to decrease offset that many times)

Well this can be done without using Segment Tree as well by just using operations on presum array and considering cases while querying. I don’t know if this is intended or not but this process fits in the time limit!
Here’s a link to my AC code : Link.
Feel free to ask anything that is not clear :slight_smile:

can u show ur code?