Binary Indexed Tree

FloatingMedianとProductOfPricesとUVa 10909で動くのを確認。

template<class T>
class BIT{
public:
  BIT(int n) : n(n), tree(n) {}
  T read(int idx) { // returns 0 if idx is smaller than 0
    T ret = 0;
    for (; idx >= 0; ret += tree[idx], idx = (idx & (idx + 1)) - 1);
    return ret;
  }
  T read(int idxl, int idxr) { // both are inclusive
    return read(idxr) - read(idxl - 1);
  }
  void update(int idx, T val){
    for (; idx < n; tree[idx] += val, idx |= idx + 1);
  }
  int getk(T k) {
    if (read(n - 1) < k) return -1;
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (read(mid) >= k) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  }
private:
  vector<T> tree;
  int n;
};