一个数组与数组更新间隔树 [英] Interval tree of an an array with update on array

问题描述

给定阵列的大小为N，并且间隔也大小为N的阵列，第一阵列的每个连续段，我需要处理Q的查询更新数组的元素，并且要求的总和段第二阵列（在第i个时间间隔为第j个间隔的元素的总和）在

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).

现在，第一查询可以容易地处理。我可以建立从数组段树。我可以用它来计算第一阵列（第二阵列中的元素）中的时间间隔的总和。但如何处理在澳第二个查询（log n）的？在最坏的情况下，我更新元素将在第二阵列中的所有时间间隔。

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.

我需要一个Ô（Q的日志N）或O-（Q 的（logN）的^ 2）解决方案。

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

推荐答案

下面是一个 O（（Q + N）* SQRT（Q））解决方案（这是基于开方分解的pretty的标准计）：
1.假设该阵列从不更新。那么这个问题就变得pretty的方便：使用preFIX款项，就可以解决 O（N）为precomputation和时间这个问题 O（1）每次查询（需要2 preFIX总和阵列的位置：一个是原始数组，另一个为间隔的数组）。
2.现在，让我们将我们的查询到大小的sqrt（Q）块。在每个块的开始，我们就可以做同样的事情在1考虑到帐户只有那些发生此块开始之前的更新。它可以在线性时间（使用两次preFIX款项）来完成。这种计算的总数是 Q / SQRT（Q）= SQRT（Q）的倍（因为它是块我们的数量）。到目前为止，它给我们 O（（N + Q）* SQRT（Q））的时间总和。
3.当我们2型的查询，都认为是当前块以外的更新已经开始考虑。因此，有最多的sqrt（Q）更新，可能会影响到答案。因此，让我们处理它们几乎是天真地：迭代发生此查询之前，在当前块内的所有更新和更新应答。要做到这一点，我们需要知道多少次的阵列在一个给定的位置是present的间隔时间从我到Ĵ。这部分可以脱机使用扫描线算法 0（Q *开方（N + Q））时间和空间（额外的日志因素没有出现，因为基数排序可以得到解决使用）。

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).

所以，我们得到 O（（N + Q）* SQRT（Q））的时间，在最坏的情况下总空间。它比 0差（Q *日志N），当然，但应该能正常运行约 10 ^ 5 查询和数组元素。

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.

这篇关于一个数组与数组更新间隔树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！