Fenwick (Binary Indexed) Trees ~ Ankur's Blog

Youtube Video:

Algorithms live

Bangla Tutorial

Implementation 01:

//Space Complexity: O(N)
// Time Complexity: O(NlogN)
#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 10005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

int BIT[MAX], n;
int a[MAX] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

void update(int x, int val)
{
    for(; x <= n; x += x & (-x))
        BIT[x] += val;
}

int query(int x)
{
    int sum = 0;
    for(; x > 0; x -= x & (-x))
        sum += BIT[x];
    return sum;
}

int main()
{
    //FASTIO
    ///*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
    //*/
    scanf("%d", &n);
    int i;
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        update(i, a[i]);
    }
    printf("sum of first 10 elements is %d\n", (query(10)) );
    printf("sum of all elements in range [2, 7] is %d\n", (query(7) - query(2 - 1)) );

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

    return 0;
}