Fenwick Tree Operations

The Fenwick Tree supports the following operations:

1. Update a value at an index

To update a value at a specific index in the Fenwick Tree, we can use the update function. This function takes in the Fenwick Tree array, the index of the value to be updated, and the new value. It then updates the value at the given index and also updates the prefix sums of all subsequent indices. Here's an example implementation in C++:

1#include <iostream>
2using namespace std;
3
4// Update a value at an index
5void update(int fenwick[], int idx, int val) {
6  int n = sizeof(fenwick) / sizeof(fenwick[0]);
7
8  while (idx < n) {
9    fenwick[idx] += val;
10    idx += idx & -idx;
11  }
12}

2. Get the prefix sum up to a given index

To calculate the prefix sum up to a given index, we can use the getPrefixSum function. This function takes in the Fenwick Tree array and the index. It then iteratively adds the values at each index to the sum variable until it reaches the given index. Here's an example implementation in C++:

1#include <iostream>
2using namespace std;
3
4// Get the prefix sum up to a given index
5int getPrefixSum(int fenwick[], int idx) {
6  int sum = 0;
7
8  while (idx > 0) {
9    sum += fenwick[idx];
10    idx -= idx & -idx;
11  }
12
13  return sum;
14}

3. Get the sum of values in a given range

To compute the sum of values within a given range, we can use the getRangeSum function. This function takes in the Fenwick Tree array, the starting index of the range, and the ending index of the range. It then calculates the prefix sum at the ending index and subtracts the prefix sum at the starting index - 1 to get the range sum. Here's an example implementation in C++:

1#include <iostream>
2using namespace std;
3
4// Get the sum of values in a given range
5int getRangeSum(int fenwick[], int start, int end) {
6  return getPrefixSum(fenwick, end) - getPrefixSum(fenwick, start - 1);
7}

Here's an example usage of the Fenwick Tree operations:

1#include <iostream>
2using namespace std;
3
4int main() {
5  int fenwick[10] = {0};
6
7  // Perform some updates
8  update(fenwick, 2, 3);
9  update(fenwick, 5, 2);
10  update(fenwick, 8, 7);
11
12  // Compute sums
13  int sum1 = getPrefixSum(fenwick, 5);
14  int sum2 = getRangeSum(fenwick, 2, 8);
15
16  cout << "Prefix sum: " << sum1 << endl;
17  cout << "Range sum: " << sum2 << endl;
18
19  return 0;
20}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

int main() {

  // Fenwick tree operations

​

  // Update a value at an index

  void update(int fenwick[], int idx, int val) {

    int n = sizeof(fenwick) / sizeof(fenwick[0]);

​

    while (idx < n) {

      fenwick[idx] += val;

      idx += idx & -idx;

    }

  }

​

  // Get the prefix sum up to a given index

  int getPrefixSum(int fenwick[], int idx) {

    int sum = 0;

​

    while (idx > 0) {

      sum += fenwick[idx];

      idx -= idx & -idx;

    }

​

    return sum;

  }

​

  // Get the sum of values in a given range