JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
How to modify BIT to update the ranges and query the ranges? | Reply
BIT(Binary Indexed Tree) can be used in two modes, "point update, query for range" and "range update, query for point".
Suppose, idx is index, u is starting index, v is ending index and val is value to be updated.
For "point update, query for range" we can use
update(idx, val);
query(v)-query(u); for range (u,v)
For "range update, query for point", we can use
update (u, val);
update (v+1, -val);

query(idx); for the desired index 'idx'
My question is how to modify BIT so that we can update values in a given range and also can query for values in a given range?
Re: How to modify BIT to update the ranges and query the ranges? (response to post by __tendua) | Reply
The classical solution is to use segment trees + lazy propagation instead; however, there is a way to do it with binary indexed trees as well.

Let's think of the sum across a range [a,b) as a sum of the following function:
f(x) = 0 if    x<a
f(x) = k if a<=x<b
f(x) = 0 if b<=x


Now with the sum of f(0..x) as g(x):
g(x) = 0        if    x<a
g(x) = k(1+x-a) if a<=x<b
g(x) = k(  b-a) if b<=x


We'll represent g(x) as the sum of two functions:
g(x) =  u(x) + v(x)
u(x) = k(1+x-a)          if a<=x
v(x) =-k(1+x-a) + k(b-a) if b<=x


To store cumulative sums of linear functions {y = mx + c} we need to use two separate BITs, one for "m" (coefficient of x) and one for "c". The insertion of a single function would look something like this:
void insert_function(int x0,int m,int c){
  fenwick_m.add(x0,+m);
  fenwick_c.add(x0,+c);
}
 
int resolve_function(int x)
  return x*fenwick_m.get(x) + fenwick_c.get(x);
}


The neat thing about this technique is that it generalises to quadratic, cubic, etc. functions which allows some pretty nifty solutions to problems that would require a huge amount of work with segment trees. One such problem is http://www.spoj.pl/problems/PYRSUM2
Re: How to modify BIT to update the ranges and query the ranges? (response to post by hex539) | Reply
I am able to get the f(x), g(x) and then g(x) as sum of two functions but couldn't connect it to the later part. I don't understand how these f(x), g(x) are related to insert and resolve function. Also what's the meaning of "cumulative sums of linear functions {y = mx + c} "?
Re: How to modify BIT to update the ranges and query the ranges? (response to post by __tendua) | Reply
For now, restrict the problem to evaluating the total of some functions:
r(x) = ax + b if 5<=x
s(x) = cx + d if 7<=x
t(x) = ex + f if 8<=x


This becomes:
sum(x) = 0                  if    x<5
sum(x) = (    a)x + (    b) if 5<=x
sum(x) = (  c+a)x + (  d+b) if 7<=x
sum(x) = (e+c+a)x + (f+d+b) if 8<=x


and we can extend the idea to an arbitrary number of functions by storing the sum of all coefficients of x, "a", and the sum of all constant additives, "b", in two binary indexed trees. This is what the "insert" and "resolve" functions do.

This is a useful technique because we can use it to find the sum of all u(x) and v(x) for some x in O(logN) time, which as explained above can be used to update and query g(x) in O(logN) time as well, allowing both range updates and range queries using only standard binary indexed tree operations. This is done by inserting a new u(x) and a new v(x) into the function trees on every range update, and then using integration-style
int range_sum = resolve(end) - resolve(start)
to answer queries.
Re: How to modify BIT to update the ranges and query the ranges? (response to post by hex539) | Reply
Given an array of integers A1,A2,.....AN, you have to perform two types of queries in the array.

1 x y. Add 1*2 to Ax, add 2*3 to Ax+1, add 3*4 to Ax+2, add 4*5 to Ax+3, and so on until Ay.
2 x y. Find the sum of all integers from index x to index y modulo 109+7, i.e. find (Ax+Ax+1+............+Ay)mod(10^9+7).

How we can use BIT in this type of question?
RSS