您可以在 O(qlog(n)) 中执行此操作，其中 q 是查询数。
这个想法是使用 BIT（二进制索引树）
// C++ program to demonstrate Range Update
// and Range Queries using BIT
#include <iostream>
using namespace std;
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[]
int getSum(int BITree[], int index)
{
int sum = 0; // Initialize result
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse ancestors of BITree[index]
while (index>0)
{
// Add current element of BITree to sum
sum += BITree[index];
// Move index to parent node in getSum View
index -= index & (-index);
}
return sum;
}
// Updates a node in Binary Index Tree (BITree) at given
// index in BITree. The given value 'val' is added to
// BITree[i] and all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
// index in BITree[] is 1 more than the index in arr[]
index = index + 1;
// Traverse all ancestors and add 'val'
while (index <= n)
{
// Add 'val' to current node of BI Tree
BITree[index] += val;
// Update index to that of parent in update View
index += index & (-index);
}
}
// Returns the sum of array from [0, x]
int sum(int x, int BITTree1[], int BITTree2[])
{
return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);
}
void updateRange(int BITTree1[], int BITTree2[], int n,
int val, int l, int r)
{
// Update Both the Binary Index Trees
// As discussed in the article
// Update BIT1
updateBIT(BITTree1,n,l,val);
updateBIT(BITTree1,n,r+1,-val);
// Update BIT2
updateBIT(BITTree2,n,l,val*(l-1));
updateBIT(BITTree2,n,r+1,-val*r);
}
int rangeSum(int l, int r, int BITTree1[], int BITTree2[])
{
// Find sum from [0,r] then subtract sum
// from [0,l-1] in order to find sum from
// [l,r]
return sum(r, BITTree1, BITTree2) -
sum(l-1, BITTree1, BITTree2);
}
int *constructBITree(int n)
{
// Create and initialize BITree[] as 0
int *BITree = new int[n+1];
for (int i=1; i<=n; i++)
BITree[i] = 0;
return BITree;
}
// Driver Program to test above function
int main()
{
int n = 5;
// Construct two BIT
int *BITTree1, *BITTree2;
// BIT1 to get element at any index
// in the array
BITTree1 = constructBITree(n);
// BIT 2 maintains the extra term
// which needs to be subtracted
BITTree2 = constructBITree(n);
// Add 5 to all the elements from [0,4]
int l = 0 , r = 4 , val = 5;
updateRange(BITTree1,BITTree2,n,val,l,r);
// Add 2 to all the elements from [2,4]
l = 2 , r = 4 , val = 10;
updateRange(BITTree1,BITTree2,n,val,l,r);
// Find sum of all the elements from
// [1,4]
l = 1 , r = 4;
cout << "Sum of elements from [" << l
<< "," << r << "] is ";
cout << rangeSum(l,r,BITTree1,BITTree2) << "\n";
return 0;
}
一个有效的解决方案是确保两个查询都可以在 O(Log n) 时间内完成。我们使用前缀总和得到范围总和。如何确保更新以某种方式完成，以便可以快速完成前缀和？考虑在范围 [l, r] 上进行范围更新后需要前缀和 [0, k]（其中 0 <= k < n）的情况。出现三种情况，因为 k 可能位于 3 个区域中。
情况一：0 < k < l 更新查询不会影响求和查询。
情况 2：l <= k <= r 考虑一个例子：
将 2 添加到范围 [2, 4]，结果数组将是： 0 0 2 2 2 如果 k = 3 Sum from [0, k] = 4 如何得到这个结果？只需将第 l 个索引的 val 添加到第 k 个索引。更新查询后，总和增加“val*(k) – val*(l-1)”。
情况 3：k > r 对于这种情况，我们需要将“val”从第 l 个索引添加到第 r 个索引。由于更新查询，Sum 增加了“val r – val (l-1)”。
观察：案例 1：很简单，因为 sum 将保持与更新前相同。
情况 2：Sum 增加了 val k – val (l-1)。我们可以找到“val”，它类似于在范围更新和点查询文章中找到第i个元素。所以我们为范围更新和点查询维护一个 BIT，这个 BIT 将有助于找到第 k 个索引处的值。现在计算了 val * k，如何处理额外的术语 val*(l-1)？为了处理这个额外的术语，我们维护另一个 BIT (BIT2)。在第 l 个索引处更新 val * (l-1)，因此当对 BIT2 执行 getSum 查询时，将给出结果为 val*(l-1)。
案例3：案例3中的和增加了“val*r – val (l-1)”，可以使用BIT2获得该项的值。我们不是加法，而是减去“val (l-1) – val r”，因为我们可以通过添加 val (l-1) 来从 BIT2 中得到这个值，就像我们在案例 2 中所做的那样，并在每个更新操作中减去 val*r。
Update Query
Update(BITree1, l, val)
Update(BITree1, r+1, -val)
UpdateBIT2(BITree2, l, val*(l-1))
UpdateBIT2(BITree2, r+1, -val*r)
Range Sum
getSum(BITTree1, k) *k) - getSum(BITTree2, k)
资料来源：geeksforgeeks.org