BIT implementation

bit.h

#include <vector>

using std::vector;

struct BinaryIndexedTree {
 public:
  BinaryIndexedTree(int n) : tree_(n + 1, 0) {}

  // Primitive Methods

  /**
   * @param idx  index of the element
   * @param diff value to accumulate
   */
  void Accumulate(int idx, int diff) {
    for (++idx; idx < tree_.size(); idx += idx & -idx)
      tree_[idx] += diff;
  }
  /**
   * @param  n [description]
   * @return  sum of the first n elements
   */
  long long PrefixSum(int n) const {
    long long res = 0;
    for (; n > 0; n -= n & -n)
      res += tree_[n];
    return res;
  }

  // Extension Methods
  class Reference {
   public:
    operator int() {
      // idx_ := prefix.1.zeros -> prefix.0.zeros
      // idx_ - 1 := prefix.0.ons -> ... -> prefix.0.zeros
      //
      // thus they share a common parent prefix.0.zeros
      //
      // return bit_.PrefixSum(idx_) - bit_.PrefixSum(idx_ - 1);
      int idx = idx_ + 1;
      int res = bit_.tree_[idx];
      for (int lowidx = idx_, stopidx = idx - (idx & -idx); lowidx > stopidx;
          lowidx -= lowidx & -lowidx)
        res -= bit_.tree_[lowidx];
      return res;
    }
    int operator =(int value) {
      int cur_value = *this;
      bit_.Accumulate(idx_, value - cur_value);
      return value;
    }
    int operator +=(int value) {
      bit_.Accumulate(idx_, value);
      return *this;
    }
    int operator -=(int value) {
      bit_.Accumulate(idx_, -value);
      return *this;
    }
    int operator ++() {
      return *this += 1;
    }
    int operator --() {
      return *this -= 1;
    }
    int operator ++(int) {
      int value = *this;
      bit_.Accumulate(idx_, 1);
      return value;
    }
    int operator --(int) {
      int value = *this;
      bit_.Accumulate(idx_, -1);
      return value;
    }
   private:
    friend class BinaryIndexedTree;
    Reference(BinaryIndexedTree &bit, int idx) : bit_(bit), idx_(idx) {}
    BinaryIndexedTree &bit_;
    int idx_;
  };
  Reference operator [](int idx) {
    return Reference(*this, idx);
  }

 private:
  vector<int> tree_;
  friend class Reference;

};