ＢＩＴ

// セグメント木と違いメモリが 2^x で無くて良い。
// log(n) の早さで範囲内の和を検索する。
// インデックス 0 に代入すると無限ループするので注意！

// 使用する最大要素数 N_MAX を設定すること。
// 使える範囲は 1 以上 N_MAX 以下である。
// 最初にすべての領域を 0 で初期化すること。

// add(x,a);  // x 番目の項目に a を加算
// int a = sum(i); // 1 <= x <= i での和

#define N_MAX 10

struct bit{
  long long dat[N_MAX + 1];

  void init(){
    for(int i = 0; i < N_MAX; i++){
      dat[i] = 0;
    }
  }

  long long sum(int i){
    long long s = 0;
    while(i > 0){
      s += dat[i];
      i -= i & -i;
    }
    return s;
  }

  void add(int i, long long x){
    while(i <= N_MAX){
      dat[i] += x;
      i += i & -i;
    }
  }
}bit1;

bit1.init() // 初期化

bit1.add(1, 5);   // インデックス 1 に 5 を加算
bit1.add(3, 6);   // インデックス 3 に 6 を加算
//bit1.add(0, 7); // インデックス 0 は無い！

bit1.sum(7);      // 1 <= x <= 7 の要素の和を計算