[模板] 树状数组 (C++ class)

闲来无事（其实是打了两三道树状数组题），写了个树状数组模板……

 1 /*
 2     Author: hotwords
 3 */
 4 
 5 template<typename tp>
 6 class BinTree {
 7     private:
 8         int n;tp *a;
 9     public:
10         inline int lowbit(int x)const{return x&-x;}
11         int size()const{return n;}
12         void empty() {
13             if(a) delete []a;
14             n=0;a=0;
15         }
16         void clear() {
17             for(int i=1;i<=n;++i) a[i]=0;
18         }
19         void init(int w) {
20             empty();
21             n=w;
22             if(n) {
23                 a=new tp[n+1];
24                 clear();
25             }
26         }
27         void add(int x,tp y) {
28             for(;x<=n;x+=lowbit(x)) a[x]+=y;
29         }
30         tp query(int x) const {
31             tp ans=0;
32             for(;x;x-=lowbit(x)) ans+=a[x];
33             return ans;
34         }
35         tp query(int l,int r) const {
36             return query(r)-query(l-1);
37         }
38         BinTree(){n=0;a=0;}
39         ~BinTree(){empty();}
40 };

[模板] 树状数组