Advanced Operations

Fenwick Trees not only support basic operations like creating, updating, and querying the sum of elements, but they also provide more advanced operations for efficient range updates and point updates.

Range Updates

Range updates allow us to update a range of elements in the Fenwick Tree efficiently with a single operation. To perform a range update, we need to update multiple elements in the range using their corresponding update values. The update values are usually obtained through pre-processing, such as taking the difference between consecutive elements in the original array.

Here's an example of how to implement a range update operation in C++:

1void rangeUpdate(int left, int right, int value, vector<int>& tree) {
2  update(left, value, tree);
3  update(right + 1, -value, tree);
4}

xxxxxxxxxx

}

#include <iostream>

using namespace std;

​

// Fenwick Tree class

class FenwickTree {

private:

  vector<int> tree;

​

public:

  FenwickTree(int size) {

    tree.resize(size + 1);

  }

​

  void update(int index, int value) {

    while (index < tree.size()) {

      tree[index] += value;

      index += index & (-index);

    }

  }

​

  int prefixSum(int index) {

    int sum = 0;

    while (index > 0) {

      sum += tree[index];

      index -= index & (-index);

    }

    return sum;

  }

​