Binary Indexed Tree(Fenwick)

#include<iostream>
using namespace std;

#define MAX 100004

int fen[MAX],n;

//pos is 1 based
void update(int pos,int val){
    for(int i=pos;i<=n;i+= i& -i)
        fen[i]+=val;
}

int sum(int pos){
    int ans=0;
    for(int i=pos;i;i-= (i & -i))
        ans+=fen[i];
    return ans;
}