魔怔模板

线段树

struct segmenttree
{	struct node
{		int l, r
;		long long sum, tag
;}	T[maxn * 4]
;	long long repair(int p, long long k)
{		return T[p].tag += k, T[p].sum += k * (T[p].r - T[p].l + 1)
;}	void downdata(int p)
{		repair(2 * p, T[p].tag), repair(2 * p + 1, T[p].tag), T[p].tag = 0
;}	long long build(int l, int r, long long a[], int p = 1)
{		return T[p].l = l, T[p].r = r, T[p].tag = 0, (l == r ? T[p].sum = a[l] : T[p].sum = build(l, (l + r) / 2, a, 2 * p) + build((l + r) / 2 + 1, r, a, 2 * p + 1))
;}	long long add(int l, int r, long long k, int p = 1)
{		return T[p].r < l || T[p].l > r ? T[p].sum : l <= T[p].l && T[p].r <= r ? repair(p, k) : (downdata(p), T[p].sum = add(l, r, k, 2 * p) + add(l, r, k, 2 * p + 1))
;}	long long getsum(int l, int r, int p = 1)
{		return T[p].r < l || T[p].l > r ? 0 : l <= T[p].l && T[p].r <= r ? T[p].sum : (downdata(p), getsum(l, r, 2 * p) + getsum(l, r, 2 * p + 1))
;}};

字典树

struct trie
{
	struct node { int next[2]; } T[maxn * 32];
	node* operator [] (const int id) { return &T[id]; }
	int tot = 0, root = 0;
	int node() { return T[tot + 1].next[0] = T[tot + 1].next[1] = 0, ++tot; }
	void clear() { tot = 0; root = node(); }
	#define t ((x >> i) & 1) 
	void add(unsigned int x)
	{
		int p = root;
		for (int i = 31; i >= 0; i--) p = (T[p].next[t] == 0 && (T[p].next[t] = node()), T[p].next[t]);
	}
	int query(unsigned int x)
	{
		int p = root, ans = 0;
		for (int i = 31; i >= 0; i--) p = T[p].next[t ^ 1] ? (ans |= 1 << i, T[p].next[t ^ 1]) : T[p].next[t];
		return ans;
	}
	#undef t
}
T;