For example being told that the value of the function or f (i) of the index-i is an i ^ k, for k> = 0 and always stay on this matter. Given query like the following:
Add value array [i], for all a <= i <= b as v Determine the total array [i] f (i), for each a <= i <= b (remember the previous function values clarification)
To work on this matter, can be formed into Query (x) = m * g (x) - c,
where g (x) is f (1) + f (2) + ... + f (x).
To accomplish this, we need to know the values of m and c. For that, we need 2 separate BIT. Observations below for each update in the form of ab v. To calculate the value of m, virtually identical to the Range Update - Point Query. We can get the following observations for each value of i, which may be:
i <a, m = 0
a <= i <= b, m = v
b <i, m = 0
By using the following observation, it is clear that the Range Update - Point Query can be used on any of the BIT. To calculate the value of c, we need to observe the possibility for each value of i, which may be:
i <a, then c = 0
a <= i <= b, then c = v * g (a - 1)
b <i, c = v * (g (b) - g (a - 1))
Again, we need Range Update - Point Query, but in a different BIT. Oiya, for a little help, I wrote the value of g (x) for k <= 3 yes: p:
k = 0 -> x
k = 1 -> x * (x + 1) / 2
k = 2 -> x * (x + 1) * (2x + 1) / 6
k = 3 -> (x * (x + 1) / 2) ^ 2
Now, example problem SPOJ - Horrible Queries . This problem is similar issues that have described, with k = 0. Note also that sometimes there is a matter that is quite extreme, where the function is not for one type of k, but it could be some that polynomial shape! Eg LA - Alien Abduction Again . To work on this problem, the solution is, for each rank we make its BIT counter m respectively. BIT combined to clear the counters c it was fine.
How can we used this concept if:
Given an array of integers A1,A2,…AN.
Given 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.
Then return Sum of the range [Ax,Ay].