给定一个大小为 N 的数组，以及一个大小为 N 的区间数组，每个数组都是第一个数组的连续段，我需要处理 Q 查询，这些查询更新数组的元素并询问第二个数组（第 i 个区间到第 j 个区间的元素之和）。
现在，可以轻松处理第一个查询。我可以从数组中构建一个段树。我可以用它来计算第一个数组（第二个数组中的一个元素）中间隔的总和。但是我如何处理 O(log n) 中的第二个查询？在最坏的情况下，我更新的元素将在第二个数组的所有间隔中。
我需要 O(Q log N) 或 O(Q (logN)^2) 解决方案。
这是一个O((Q + N) * sqrt(Q))解决方案（它基于一个非常标准的 sqrt-decomposition 思想）：
1. 假设数组永远不会更新。那么问题就变得很简单了：使用前缀和，可以及时解决这个问题，O(N)以便进行预计算和O(1)每次查询（我们需要 2 个前缀和数组：一个用于原始数组，另一个用于间隔数组）。
2. 现在让我们将查询分成大小为 的块sqrt(Q)。在每个块的开头，我们可以做与 1 中相同的事情。只考虑在该块开始之前发生的那些更新。它可以在线性时间内完成（使用两次前缀和）。此类计算的总数为Q / sqrt(Q) = sqrt(Q)次（因为它是我们拥有的块数）。到目前为止，它O((N + Q) * sqrt(Q))总共给了我们时间。
3. 当我们得到类型 2 的查询时，所有在当前块之外的更新都已经被考虑了。因此，最多sqrt(Q)有可能影响答案的更新。因此，让我们几乎天真地处理它们：迭代当前块内发生在此查询之前的所有更新并更新答案。为此，我们需要知道数组中的给定位置在从i到的区间中出现了多少次j。这部分可以通过使用O(Q * sqrt(N + Q))时间和空间的扫线算法离线解决（不会出现额外的对数因子，因为可以使用基数排序）。
所以我们O((N + Q) * sqrt(Q))在最坏的情况下得到时间和空间。当然，它比 更糟糕O(Q * log N)，但对于10^5查询和数组元素应该可以正常工作。