To update a value in a Fenwick Tree, we need to make two changes: update the original array and update the prefix sum in the Fenwick Tree. Let's say we want to update the value at index i with a new value val.
In order to update the original array, we simply assign the new value val to arr[i].
TEXT/X-C++SRC
1int index = i;
2int value = val;
3arr[index] = value;To update the prefix sum in the Fenwick Tree, we need to find the difference between the new value val and the old value arr[i]. Let's call this difference diff. Then, we update the Fenwick Tree by adding diff to the prefix sum at each index that represents the range where the value at index i contributes.
TEXT/X-C++SRC
1void update(int BIT[], int n, int i, int val) {
2 while (i <= n) {
3 BIT[i] += val;
4 i += i & (-i);
5 }
6}Let's see an example of how to update a value in a Fenwick Tree using C++:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4const int n = 10;
5int arr[n + 1] = {0};
6int BIT[n + 1] = {0};
7
8// Update the value at index i in the Fenwick Tree
9void update(int BIT[], int n, int i, int val) {
10 // Adding the updated value at index i
11 while (i <= n) {
12 BIT[i] += val;
13 i += i & (-i);
14 }
15}
16
17int main() {
18 // Updating value at index 5 to 10
19 int index = 5;
20 int value = 10;
21 int diff = value - arr[index];
22 arr[index] = value;
23 update(BIT, n, index, diff);
24
25 return 0;
26}xxxxxxxxxx26
using namespace std;// Update the value at index i in the Fenwick Treevoid update(int BIT[], int n, int i, int val) { // Adding the updated value at index i while (i <= n) { BIT[i] += val; i += i & (-i); }}int main() { const int n = 10; int arr[n + 1] = {0}; int BIT[n + 1] = {0}; // Updating value at index 5 to 10 int index = 5; int value = 10; int diff = value - arr[index]; arr[index] = value; update(BIT, n, index, diff); return 0;}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment