Given an array arr[0..n-1]. The following operations need to be performed.

**update(l, r, val)**: Add ‘val’ to all the elements in the array from [l, r].**getRangeSum(l, r)**: Find sum of all elements in array from [l, r].

Initially all the elements in the array are 0. Queries can be in any oder, i.e., there can be many updates before range sum.

**Example:
**

Input : n = 5 // {0, 0, 0, 0, 0} Queries: update : l = 0, r = 4, val = 2 update : l = 3, r = 4, val = 3 getRangeSum : l = 2, r = 4 Output: Sum of elements of range [2, 4] is 12 Explanation : Array after first update becomes {2, 2, 2, 2, 2} Array after second update becomes {2, 2, 2, 5, 5}

In the previous post, we discussed range update and point query solutions using BIT.

rangeUpdate(l, r, val) : We add ‘val’ to element at index ‘l’. We subtract ‘val’ from element at index ‘r+1’.

getElement(index) [or getSum()]: We return sum of elements from 0 to index which can be quickly obtained using BIT.

We can compute rangeSum() using getSum() queries.

rangeSum(l, r) = getSum(r) – getSum(l-1)

A **Simple Solution **is to use solutions discussed in previous post. Range update query is same. Range sum query can be achieved by doing get query for all elements in range.

An** Efficient Solution **is to make sure that both queries can be done in O(Log n) time. We get range sum using prefix sums. How to make sure that update is done in a way so that prefix sum can be done quickly? Consider a situation where prefix sum [0, k] (where 0 <= k < n) is needed after range update on range [l, r]. Three cases arises as k can possibly lie in 3 regions.

**Case 1**: 0 < k < l

The update query won’t affect sum query.

**Case 2**: l <= k <= r

Consider an example:

Add 2 to range [2, 4], the resultant array would be: 0 0 2 2 2 If k = 3 Sum from [0, k] = 4

How to get this result?

Simply add the val from l^{th} index to k^{th} index. Sum is incremented by “val*(k) – val*(l-1)” after update query.

**Case 3**: k > r

For this case, we need to add “val” from l^{th} index to r^{th} index. Sum is incremented by “val*r – val*(l-1)” due to update query.

**Observations :**

**Case 1:** is simple as sum would remain same as it was before update.

**Case 2:** Sum was incremented by val*k – val*(l-1). We can find “val”, it is similar to finding the i^{th} element in range update and point query article. So we maintain one BIT for Range Update and Point Queries, this BIT will be helpful in finding the value at k^{th} index. Now val * k is computed, how to handle extra term val*(l-1)?

In order to handle this extra term, we maintain another BIT (BIT2). Update val * (l-1) at l^{th} index, so when getSum query is performed on BIT2 will give result as val*(l-1).

**Case 3 :** The sum in case 3 was incremented by “val*r – val *(l-1)”, the value of this term can be obtained using BIT2. Instead of adding, we subtract “val*(l-1) – val*r” as we can get this value from BIT2 by adding val*(l-1) as we did in case 2 and subtracting val*r in every update operation.

Update QueryUpdate(BITree1, l, val) Update(BITree1, r+1, -val) UpdateBIT2(BITree2, l, val*(l-1)) UpdateBIT2(BITree2, r+1, -val*r)Range SumgetSum(BITTree1, k) *k) - getSum(BITTree2, k)

C++ Implementation of above idea

`// 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) << ` ```
"
"
``` `; ` ` ` ` ` `return` `0; ` `} ` |

Output:

Sum of elements from [1,4] is 50

**Time Complexity** : O(q*log(n)) where q is number of queries.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments