BinaryIndexTree.h

Go to the documentation of this file.

#ifndef   dsa_BinaryIndexTree_H__
#define   dsa_BinaryIndexTree_H__

#include <cstdlib>

#include <vector>
#include <algorithm>

namespace meow {

template<class Value>
class BinaryIndexTree {
private:
  std::vector<Value> array_;
public:
  BinaryIndexTree() {
  }

  BinaryIndexTree(size_t size, Value const& value):
  array_(size, value) {
  }

  BinaryIndexTree(BinaryIndexTree const& tree2):
  array_(tree2.array_) {
  }

  void reset(size_t size, Value const& init) {
    array_.clear();
    array_.resize(size, init);
  }

  void update(size_t index, Value const& value) {
    index++;
    for ( ; index <= array_.size(); index += (index & -index)) {
      array_[index - 1] = array_[index - 1] + value;
    }
  }


  Value query(ssize_t index) const {
    index = std::min(index + 1, (ssize_t)array_.size());
    Value ret(0);
    for ( ; 0 < index; index -= (index & -index)) {
      ret = ret + array_[index - 1];
    }
    return ret;
  }
};

}

#endif // dsa_BinaryIndexTree_H__