树状数组
代码模版：
#include <bits/stdc++.h>
using namespace std;
int a[500010], b[500010], sum[500010], n, m, x, k, op;
int lowbit(int x) {return x & -x;}
void init() {
for (int i = 1; i <= n; i++) {
sum[i] = a[i] + sum[i - 1];
b[i] = sum[i] - sum[i - lowbit(i)];
}
}
void add(int x, int k) {
while (x <= n) {
b[x] += k;
x += lowbit(x);
}
}
int getsum(int x) {
int ans = 0;
while(x) {
ans += b[x];
x -= lowbit(x);
}
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
init();
while (m--) {
cin >> op >> x >> k;
if (op == 1) add(x, k);
else cout << getsum(k) - getsum(x - 1) << "\n";
}
return 0;
}
Trie树
代码模版
struct trie{
int tr[10010][26], cnt;
bool word[10010];
void insert(string s, int len) {
int pos = 0;
for (int i = 0; i < len; i++) {
int id = s[i] - 'a';
if (!tr[pos][id]) tr[pos][id] = ++cnt;
pos = tr[pos][id];
}
word[pos] = 1;
}
bool find(string s, int len) {
int pow = 0;
for (int i = 0; i < len; i++) {
int id = s[i] - 'a';
if (!tr[pos][id]) return 0;
pos = tr[pos][id];
}
return word[pos];
}
};