meowpp/dsa/BinaryIndexTree.hpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include "BinaryIndexTree.h"

#include <cstdlib>

#include <vector>
#include <algorithm>


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;
  }
}