Binary Indexed Tree

Implementation:

Note that arrays are 1-based.

#include <iostream>
#include <cstring> // memset
#define max_n 50001

using namespace std;

void fenwick_init(int data[]) {
    memset(data, 0, sizeof data);
}

void fenwick_update(int data[], int data_length, int at, int val) {
    for(; at < data_length; at += at & -at)
    {   cout << at << endl;
        data[at] += val;
    }
}

int fenwick_query(int data[], int at) {
    int sum = 0;
    for(; at > 0; at &= at - 1)
        sum += data[at];
    return sum;
}

int main() {
    int data[max_n];
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};

    fenwick_init(data);

    for(int i = 1; i <= sizeof(arr) / sizeof(arr[0]); i++)
        fenwick_update(data, max_n, i, arr[i-1]);

    for(int i = 1; i <= 8; i++)
        cout << fenwick_query(data, i) << " " << i*(i+1)/2 << endl;
    return 0;
}