Creating a Fenwick Tree

To create a Fenwick Tree, we need to implement the necessary methods: update and query.

The update method is used to update the value of an element in the Fenwick Tree. It takes two parameters: index and value. Starting from the given index, we update the corresponding values in the tree by adding the value. We continue updating until we reach the end of the tree or go out of bounds.

Here's an example of how to implement the update method in C++:

1void update(int index, int value) {
2  while (index < tree.size()) {
3    tree[index] += value;
4    index += index & (-index);
5  }
6}

The query method is used to calculate the sum of elements in a given range from index 1 to the given index. It takes one parameter: index. Starting from the given index, we calculate the sum by iterating through the tree, adding the values at each index. We continue iterating until we reach 0.

Here's an example of how to implement the query method in C++:

1int query(int index) {
2  int sum = 0;
3  while (index > 0) {
4    sum += tree[index];
5    index -= index & (-index);
6  }
7  return sum;
8}

Let's create a Fenwick Tree with a size of 10 and perform an update operation at index 5 with a value of 3. Then, we'll perform a query operation at index 8 and print the result:

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

class FenwickTree {

  std::vector<int> tree;

​

public:

  FenwickTree(int n) {

    tree.resize(n + 1, 0);

  }

​

  void update(int index, int value) {

    while (index < tree.size()) {

      tree[index] += value;

      index += index & (-index);

    }

  }

​

  int query(int index) {

    int sum = 0;

    while (index > 0) {

      sum += tree[index];

      index -= index & (-index);

    }

    return sum;

  }

};

​

int main() {