Querying a Fenwick Tree

To answer range sum queries on a Fenwick Tree, we can use the query method. This method takes one parameter: the index of the element up to which we want to calculate the sum. Starting from the given index, we traverse the Fenwick Tree by moving to the parent node until we reach the root or go out of bounds. At each node, we add the value stored at that node to the running sum. Finally, we return the sum as the result of the query.

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

1int query(int index, vector<int>& tree) {
2  int sum = 0;
3
4  while (index > 0) {
5    sum += tree[index];
6
7    // Move to the parent
8    index -= index & (-index);
9  }
10
11  return sum;
12}

In the above code, we start with a sum of 0 and iterate through the tree starting from the given index. At each node, we add the value stored at that node to the sum. We then move to the parent node by subtracting the least significant bit (obtained by using the & operator with the two's complement of the index). This process continues until we reach the root of the tree or go out of bounds.

Let's create a Fenwick Tree with a size of 11 and perform some update operations. Then, we'll perform a query operation at index 10 to calculate the sum of all elements up to that index and print the result.

xxxxxxxxxx

}

#include <iostream>

#include <vector>

​

using namespace std;

​

// Querying a Fenwick Tree

​

int query(int index, vector<int>& tree) {

  int sum = 0;

​

  while (index > 0) {

    sum += tree[index];

​

    // Move to the parent

    index -= index & (-index);

  }

​

  return sum;

}

​

int main() {

  // Create a Fenwick Tree

  vector<int> tree(11, 0);

​

  // Update elements

  tree[3] += 5;

  tree[6] += 9;

  tree[8] += 2;

  tree[9] += 7;