BIT_TREE的c++模板

例题POj2352 http://poj.org/problem?id=2352

1 template
     
       2 class bit_tree { 3 private : 4     T *tree; 5     T _val; 6     int _size; 7 public : 8     bit_tree(int in_size = 0, T in_val = 0) { 9         _size = in_size;10         tree = new T[_size];11         _val = in_val;12         fill(tree, tree + _size, _val);13     }14     ~bit_tree() {15         delete[] tree;16     }17     inline void clear() {18         fill(tree, tree + _size, _val);19     }20     inline int lowbit(int pos) {21         return pos & (-pos);22     }23 24     void modify(int pos, T v) {25         if (pos <= _size) {26             while (pos < _size) {27                 tree[pos] += v;28                 pos += lowbit(pos);29             }30         }31     }32 33     T query(int pos) {34         T ret = 0;35         if (pos <= _size) {36             while (pos > 0) {37                 ret += tree[pos];38                 pos -= lowbit(pos);39             }40         }41         return ret;42     }43 };