Updating a Value in a Fenwick Tree
Once a Fenwick Tree is constructed, you may need to update the value in a specific position. To update a value in a Fenwick Tree, follow these steps:
Calculate the difference between the new value and the old value.
TEXT/X-C++SRC1// Compute the difference 2int diff = new_value - old_value;Update the specific position in the Fenwick Tree with the difference.
TEXT/X-C++SRC1// Update the value in the Fenwick Tree 2int index = position; 3while (index <= n) { 4 fenwickTree[index] += diff; 5 index = index + (index & -index); 6}
Here's a complete C++ code that demonstrates how to update a value in a Fenwick Tree:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4void updateValue(int fenwickTree[], int position, int new_value, int n) {
5 // Compute the difference
6 int diff = new_value - fenwickTree[position];
7
8 // Update the value in the Fenwick Tree
9 int index = position;
10 while (index <= n) {
11 fenwickTree[index] += diff;
12 index = index + (index & -index);
13 }
14}
15
16int main() {
17 int fenwickTree[] = {0, 1, 3, -2, 4, 6, 1, 2};
18 int position = 4;
19 int new_value = 5;
20 int n = sizeof(fenwickTree) / sizeof(fenwickTree[0]);
21
22 // Update value in Fenwick Tree
23 updateValue(fenwickTree, position, new_value, n);
24
25 // Print updated Fenwick Tree
26 for (int i = 1; i <= n; i++) {
27 cout << fenwickTree[i] << " ";
28 }
29
30 return 0;
31}