SPOJ CTRICK, RRSCHED, ASSIST

abeyaar · December 30, 2014, 6:30pm

pushkarmishra/SPOJ/blob/master/CTRICK.cpp

/*
Algo: Binary Indexed Tree
Complexity: N*LogN
*/

#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 20500
#define init(Arr) memset((Arr), 0, sizeof (Arr))
 
static int BIT[MAX+1], ANS[MAX], N, T;
inline void update(int i, int v){
    for (; i<=MAX; i+=(i & -i)) BIT[i]+=v;
}
inline int query(int i){
    int ans=0;
    for (; i>0; i-=(i & -i)) ans+=BIT[i];
    return ans;
}

This file has been truncated. show original

All these problems are similar.
Can anyone explain how to come up with a BIT solution here??