一、 树状数组
1. lowbit
x&-x，没了
2. 上代码!
void add(int p,int k){
while(p<=n){
d[p] += k;
p += lowbit(p);
}
}
int query(int x){
int ans = 0;
while(x>0){
ans += d[x];
x -= lowbit(x);
}
return ans;
}
3. 超级树状数组(干爆线段树)
题目：P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&-(x))
using namespace std;
int n,m,x,y,d1[500002],d2[500002],o,a[500002],k;
void add(int* d,int p,int k){
while(p<=n){
d[p] += k;
p += lowbit(p);
}
}
int query(int* d,int x){
int ans = 0,idx = x;
while(x>0){
ans += d[x];
x -= lowbit(x);
}
return ans+a[idx];
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> x;
add(d1,i,x-y);
add(d2,i,(x-y)*(i-1));
y = x;
}
for(int i=1;i<=m;i++){
cin >> o >> x >> y;
if(o==1){
cin >> k;
add(d1,x,k); add(d1,y+1,-k);
add(d2,x,k*(x-1)); add(d2,y+1,-k*y);
}
else if(o==2) cout << (y*query(d1,y)-(x-1)*query(d1,x-1))-(query(d2,y)-query(d2,x-1)) << '\n';
}
return 0;
}
二、Trie
1. 普通trie
class trie{
private:
int son[50002][3],siz[50002],cnt;
bool isword[50002];
public:
void insert(string s){
int len = s.size(),pos = 0;
for(int i=0;i<len;i++){
int idx = s[i]-'a'; siz[pos]++;
if(!son[pos][idx]) son[pos][idx] = ++cnt;
pos = son[pos][idx];
}
isword[pos] = 1,siz[pos]++;
}
bool find(string s){
int len = s.size(),pos = 0;
for(int i=0;i<len;i++){
int idx = s[i]-'a';
if(!son[pos][idx]) return 0;
pos = son[pos][idx];
}
return isword[pos];
}
};
2. 01-trie
不会(雾)