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
| class Fenwick{
vector<int> s;
int n;
public:
Fenwick(int n):n(n),s(n+1){}
int lowbit(int x){
return x&(-x);
}
void add(int i){
while(i<=n){
s[i]++;
i+=lowbit(i);
}
}
int pre(int i){
int res=0;
while(i>0){
res+=s[i];
i-=lowbit(i);
}
return res;
}
int query(int l,int r){
return pre(r)-pre(l-1);
}
};
|