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 Algorithm Discussions Skill-building and Educational Discussion for Algorithm How to modify BIT to update the ranges and query the ranges?
 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
 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?
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm How to modify BIT to update the ranges and query the ranges? Previous Thread  |  Next Thread