Interval tree of an an array with update on array

Question

Given a array of size N, and an array of intervals also of size N, each a contiguous segment of the first array, I need to handle Q queries that update the elements of the array and that ask for the sum of an segment in the second array (sum of the elements in the iTH interval to the jTH interval).

Now, the first query can be handled easily. I can build a segment tree from the array. I can use it to calculate the sum of an interval in the first array (an element in the second array). But how can i handle the second query in O(log n)? In the worst case, the element I update will be in all the intervals in the second array.

I need a O(Qlog N) or O(Q(logN)^2) solution.

Answer 1

Here is an O((Q + N) * sqrt(Q)) solution(it is based on a pretty standard idea of sqrt-decomposition):
1. Let's assume that the array is never updated. Then the problem becomes pretty easy: using prefix sums, it is possible to solve this problem in O(N) time for precomputation and O(1) per query(we need 2 prefix sum arrays here: one for the original array and the other one for the array of intervals).
2. Now let's divide our queries into blocks of size sqrt(Q). In the beginning of the each block, we can do the same thing as in 1. taking into accounts only those updates that happened before the beginning of this block. It can be done in linear time(using prefix sums twice). The total number of such computations is Q / sqrt(Q) = sqrt(Q) times(because it is the number of blocks we have). So far, it gives us O((N + Q) * sqrt(Q)) time in total.
3. When we get the query of type 2, all the updates that are outside the current block are already considered. So there are at most sqrt(Q) updates that could affect the answer. So let's process them almost naively: iterate over all updates within the current block that happened before this query and update the answer. To do this, we need to know how many times a given position in the array is present in the intervals from i to j. This part can be solved offline with sweep line algorithm using O(Q * sqrt(N + Q)) time and space(additional log factor does not appear because radix sort can be used).

So we get O((N + Q) * sqrt(Q)) time and space in the worst case in total. It is worse than O(Q * log N), of course, but should work fine for about 10^5 queries and array elements.