JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor segment tree, a simple question
 segment tree, a simple question | Reply Hi,I have a simple question about segment tree :we have an array of siz n and two queries1) add i j k : add k to a[i],a[i+1],...,a[j]2) max i j : return maximum value between a[i],a[i+1],...,a[j]How can I solve this problem ??Thx in advance.
 Re: segment tree, a simple question (response to post by biohazardacm) | Reply You can store one additional field in each node which specifies how much was added to the corresponding segment. To find maximum in a node you'll have to count the sum of these values along the way to the root. This can be done by recursion with one additional parameter, sum so far.
 Re: segment tree, a simple question (response to post by it4.kp) | Reply So ur algorithm answer two queries in o(log n) ??your add method is like that ???```void add(int x,int y,int i){ if(i>y || j=i && y<=j){ s[i]+=k; return; } add(x, (x+y)/2, 2*i+1); add((x+y)/2+1, y, 2*i+2); } ```if YES, Could you write method of finding max ??
 Re: segment tree, a simple question (response to post by biohazardacm) | Reply you can do that with that is called "late update".you update segments as it4.kp suggested, and when there is a max query, you resolve what you have saved in those additional fields. But you should resolve only those which are related, so you get logn for both queries.(since you can resolve at most 2 with MAX query)Also, while resolving, don't do unneccessary resolve operations. for example, if you are going to resolve the additional field of [i,i+k] for a query like [i,i+5] and [i,i+5] is included in the [i,i+k/2] part, then just pump the additional value to both childs of [i,i+k] (namely [i,i+k/2] and [i+k/2+1 , i+k]) and resolve [i,i+k/2] part because you only need that part.
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor segment tree, a simple question Previous Thread  |  Next Thread