JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
segment tree, a simple question | Reply
Hi,

I have a simple question about segment tree :

we have an array of siz n and two queries

1) 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<x) return;
	if(x>=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.
RSS