1 files changed, 44 insertions, 0 deletions
diff --git a/meowpp/dsa/BinaryIndexTree.hpp b/meowpp/dsa/BinaryIndexTree.hpp
new file mode 100644
index 0000000..e7e146a
--- /dev/null
+++ b/meowpp/dsa/BinaryIndexTree.hpp
@@ -0,0 +1,44 @@
+
+namespace meow{
+  template<class Value>
+  inline
+  BinaryIndexTree<Value>::BinaryIndexTree():
+  _array(0){
+  }
+  template<class Value>
+  inline
+  BinaryIndexTree<Value>::BinaryIndexTree(size_t __size, Value const& __value):
+  _array(__size, __value){
+  }
+  template<class Value>
+  inline
+  BinaryIndexTree<Value>::BinaryIndexTree(BinaryIndexTree const& __tree2):
+  _array(__tree2._array){
+  }
+  //
+  template<class Value>
+  inline void
+  BinaryIndexTree<Value>::reset(size_t __size, Value const& __init){
+    _array.clear();
+    _array.resize(__size, __init);
+  }
+  //
+  template<class Value>
+  inline void
+  BinaryIndexTree<Value>::update(size_t __index, Value const& __value){
+    __index++;
+    for( ; __index <= _array.size(); __index += (__index & -__index)){
+      _array[__index - 1] = _array[__index - 1] +  __value;
+    }
+  }
+  template<class Value>
+  inline Value
+  BinaryIndexTree<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;
+  }
+}