Updating a Fenwick Tree
Once a Fenwick Tree is built, we can perform updates on it efficiently. Updating a Fenwick Tree involves modifying the values of the original array and recalculating the prefix sum values for the affected elements.
To update a Fenwick Tree, we need to follow these steps:
- Find the index of the element in the original array that needs to be updated.
- Calculate the difference between the new value and the current value at that index.
- Update the element in the original array with the new value.
- Traverse the Fenwick Tree in a bottom-up manner, starting from the given index.
- In each step, add the calculated difference to the value at the current index.
- Update the index to its parent index by adding the value of the rightmost set bit.
- Repeat steps 5 to 6 until the index becomes equal to or greater than the size of the Fenwick Tree.
Let's see an example of how to perform an update on a Fenwick Tree in C++:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4// Function to update the value of an element in the original array
5void updateValue(int arr[], int bit[], int n, int index, int newValue) {
6 // Calculate the difference between new and current values
7 int difference = newValue - arr[index];
8 // Update the element in the original array
9 arr[index] = newValue;
10
11 index++;
12 // Traverse the Fenwick Tree and update the values
13 while (index <= n) {
14 bit[index] += difference;
15 index += index & -index;
16 }
17}
18
19// Usage
20int main() {
21 int arr[] = {1, 3, 2, -5, 4, 6};
22 int n = sizeof(arr) / sizeof(arr[0]);
23 int* bit = buildFenwickTree(arr, n);
24
25 // Update the value at index 3 to 8
26 updateValue(arr, bit, n, 3, 8);
27
28 cout << "Updated Array: ";
29 for (int i = 0; i < n; i++) {
30 cout << arr[i] << " ";
31 }
32 cout << endl;
33
34 return 0;
35}