1#include <iostream>
2using namespace std;
3
4// Function to update the value at a given index
5void update(int bit[], int n, int index, int value) {
6    index++;
7
8    while (index <= n) {
9        // Adding value to current index
10        bit[index] += value;
11
12        // Update index to its parent
13        index += index & -index;
14    }
15}
16
17// Function to get the prefix sum of elements up to a given index
18int getPrefixSum(int bit[], int index) {
19    index++;
20    int sum = 0;
21
22    while (index > 0) {
23        // Adding value at current index to sum
24        sum += bit[index];
25
26        // Update index to its parent
27        index -= index & -index;
28    }
29
30    return sum;
31}
32
33// Function to build a Fenwick Tree
34int* buildFenwickTree(int arr[], int n) {
35    // Creating a Fenwick Tree with n+1 elements
36    int* bit = new int[n + 1];
37
38    // Initializing all elements of the Fenwick Tree to 0
39    for (int i = 0; i <= n; i++) {
40        bit[i] = 0;
41    }
42
43    // Updating the Fenwick Tree using all elements of the array
44    for (int i = 0; i < n; i++) {
45        update(bit, n, i, arr[i]);
46    }
47
48    // Returning the Fenwick Tree
49    return bit;
50}