CodeArchive BinaryIndexedTree

Yury's version of Binary Indexed Tree (untested)

const int sz = (1 << 24);
int help[sz];
int getcs(int ind){ for(int out = help[ind]; ; out += help[ind &= (ind - 1)]) if(!ind) return out; }
void addind(int ind) { if(ind) while(ind < sz) help[ind]++, ind += (ind & -ind); else help[ind]++; }

Binary Indexed Tree

A compressed binary index tree for solving the dynamic partial (cumulative) sum problem.

Used evilly by Yury to solve the BlackBox problem in UVA

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

const int MAX_DEPTH = 15;

int cum_sum[(1 << MAX_DEPTH) + 1];

inline void add(int idx, int v) {
  for (int i = 0; i <= MAX_DEPTH; ++i)
    if ( idx & (1 << i) ) {
      cum_sum[idx] += v;
      idx += (1 << i);
    }
}

inline int get(int idx) { // Find sum(0..idx)
  int result = 0;
  for (int i = 0; i <= MAX_DEPTH; ++i)
    if (idx & (i << i) ) {
      result += cum_sum[idx];
      idx -= i;
    }
  return result;
}

int get_nth(int n) { // Find the leftmost spot for which sum(1..r) >= n
  int idx = 1 << MAX_DEPTH;
  for (int sz = idx >> 1; sz; sz >>= 1)
    if (cum_sum[idx-sz] >= n) idx -= sz;
    else n -= cum_sum[idx-sz];
  return idx;
}

int main() {
  int num_cases;
  scanf("%d", &num_cases);
  int n,m;
  int a[32768], u[32768];
  int sorted[32768];
  while(num_cases--) {
    memset(cum_sum, 0, sizeof(cum_sum));
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", a+i);
    for (int i = 0; i < m; ++i) scanf("%d", u+i);
    memcpy(sorted, a, sizeof(sorted));
    sort(sorted, sorted+n);
    int cnt = 0, ptr = 0;
    for (int i = 0; i < m; ++i) {
      while(cnt < u[i])
        add(lower_bound(sorted, sorted+n, a[cnt++]) - sorted + 1,1);
      printf("%d\n", sorted[get_nth(++ptr) - 1]);
    }
    if (num_cases) printf("\n");
  }
  return 0;
}

-- Main.MatthewChan - 11 Feb 2006