树状数组
树状数组支持单点修改和前缀查询。通过加特技（？？？）可以让它支持更多操作
为了不断一分为二，引入一个辅助量：lowbit
假如有这么个数x，则C[x]=x-lowbit(x)+1~x所有元素权值的和。
lowbit(x)=x&-x 表示x这个数在二进制下的从右到左第一个1及后面的0.
比如4在二进制中是00000100，-4二进制表示为补码(-x=2^32-x)，就是10000100，他们两个通过与运算后的值是
00000100 &
10000100 =
00000100，即为4.所以lowbit(4)=4;
int lowbit(int x){return x&(-x)}
//c[x]=a[x-lowbit(x)+1]+…+a[x]
void add(int x,int y)
{
for(;x<=n;x-=lowbit(x))
{
c[x]+=y;
}
}
int ask(int x,int y)
{
int ans=0;
for(;x<=y;x+=lowbit(x))
{
ans+=c[x];
}
return ans;
}
//改点求段
void ADD(int x, int c)//改点
{
for (int i=x; i<=n; i+=i&(-i)) a[i] += c;//每次加上lowbit[i]，都是找到当前节点的父亲
}
int SUM(int x)//求段
{
int s = 0;
for (int i=x; i>0; i-=i&(-i)) s += a[i];//*1
return s;
}
*1：每次减去一个lowbit，都会得到前一个区间包含数字最多的那个点。比如说x当前为6，那么s+=（56）的权值和，减去lowbit以后x变为4，4包含了（14）的权值和，于是就非常高效啦
//lazytag,中午回头补
NOIP2013 火柴排队
要让a中第K大的和b中第K大的匹配。移动a,b与只移动一个没有区别，所以可以确定a,只移动b。
首先将a,b离散化，用Ai表示ai是a数组中第几大的，用Bi表示bi是b数组中第几大的。
之后定义数组C满足C[Ai]=i,定义D满足Di=C[Bi],表示b中第i项最终需要移动到哪一位。
发现移动步数相当于对D数组进行排序，只能移动相邻两项的最小步数。等价于求逆序对对数，从前向后枚举每一项，用树状数组维护，求出每一项之前比该项大的数的数量即可。
int main()
{
for(int i=1;i<=n;i++) A[i]=a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)A[i]=lower_bound(a+1,a+n+1,A[i])-a;
for(int i=1;i<=n;i++) B[i]=b[i];
sort(b+1,b+n+1);
for(int i=1;i<=n;i++) B[i]=lower_bound(b+1,b+n+1,B[i])-b;
for(int i=1;i<=n;i++)C[A[i]]=i;
//A[i]表示a[i]在a数组中是第几大的
//C[i]表示a数组中第i大的数的下标
for(int i=1;i<=n;i++)D[i]=C[B[i]];
//C[B[i]]表示a数组中第B[i]大的数的下标
//D[i]表示b数组中第i个数应该移动到哪个位置//一定为1~n的全排列
for(int i=n;i>=1;i–)
{
ans+=ask(D[i]),add(D[i],1);
}
}
野鸡题(???)
区间加一个数，区间求和
数据范围n<=100000;
用两个树状数组解决问题。给[l,r]增加x的权值的时候，在另一个树状数组上i-1处和r处加上x的权值。
注意考虑“0”的问题，因为树状数组算不了0.
在询问前x个数的和的时候只有r>x，l<=x的区间会发生问题，于是利用另一个树状数组来维护，在l加上x的权值，在r+1减去x的权值，就能快速求出满足这个条件的区间和了。
显然第二个树状数组的作用是类似与线段树中的"lazytag"的，思想就是用不到的值先不改，用到了再改。而且这样会很高效：假如当前区间之前减三，后来又加五，如果每次把区间内所有值都改了，那么既要给每个值减三，又要给每个值加五。还不如算好了这个区间总共是加二的，要访问子区间的时候往下传递这个tag：你要加二啦，就能省去很多不必要的麻烦了w
//差分数组【感谢HHM同学的代码赞助！】
/可以差分数组，差分表示每一项减前一项
例如1 3 2 4 5，差分为1 2 -1 2 1
修改区间时，原数组每项都要变化
但差分数组只在l处权值x,在r+1处权值-x
在上例中，[3,4]+2，原数组变为1 5 4 6 5
但差分数组变为1 4 -1 2 3
/
void add(int x,int y) //添加a[x]并修改前缀和
{
for(;x<=n;x+=x&-x)
c[x]+=y;
}
//ask®-ask(l-1)表示[l,r]前缀和
int ask(int x) //询问前x个数的和
{
int y=0;
for(;x;x-=x&-x)
y+=c[x];
return y;
}
while(q–)
{
int t,l,r,x;
scanf(“d%”,&t);
if(t==1)
{
scanf(“d%d%d%”,&l,&r,&x);
add(l,x);
add(r+1,-x); //[l,r]增加x权值
}
else
scanf(“d”,&x),ask(x);//查询x权值
}
/用两个树状数组实现,例：
如1 2 3 4 5//下标
0 0 0 0 0//初值
改0 3 3 3 0//改后
0 3 6 9 9//前缀和
第一个树状数组 -3 0 0 12 0
前缀和：-3 -3 -3 9 9
我们发现此时只有[l-1][r-1]是错误的，其余前缀和不变
第二个用来修正，而其前缀和与原前缀和差为3 6 9，成等差数列
故开另一个树状数组 3 0 0 -3 0
前缀和 3 3 3 0 0
前缀和每一项乘以下标 3 6 9 0 0
加上上一个树状数组的前缀和 0 3 6 9 9
(上例中l=2,x=3)
实现：/
void add1(int x,int y) //添加a[x]并修改前缀和
{
for(;x<=n;x+=x&-x)
c[x]+=y;
}
void add2(int x,int y) //添加a[x]并修改前缀和
{
for(;x<=n;x+=x&-x)
d[x]+=y;
}
int ask1(int x) //询问前x个数的和
{
int y=0;
for(;x;x-=x&-x)
y+=c[x];
return y;
}
int ask2(int x) //询问前x个数的和
{
int y=0;
for(;x;x-=x&-x)
y+=d[x];
return y;
}
add1(l-1,-x(l-1));
add1(r,xr);
add2(l-1,x);
add2(r,-x);
ask1®+ask2®r-(ask1(l-1)+ask2(l-1)(l-1))
SDOI2009 HH的项链
将所有询问按照R排序，从前向后枚举每个贝壳。
对于第i个贝壳求出前一个和它相同的贝壳F[i]，之后在树状数组上给[F[i]+1,i]这一段+1即可。
树状数组的区间+1可以变成在点F[i]+1上+1，在点i+1上-1。
询问时只要对于特定的r询问树状数组中l点的值即可。
时间复杂度O(nlogn)。
二叉搜索树
也叫平衡树（BST）。它或者是一棵空数，或者是具有下列性质的二叉树:
1.若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值。
2.若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；它的左，右子树也分别为二叉搜索树。
根据功能和实现上的差异可以分为以下几种：
基于旋转：splay,treap,AVL树……
基于重构：替罪羊树，朝鲜树
基于可并堆：fhq-treap
多数平衡树插入删除的时间复杂度为O(logn)，空间复杂度为O(n)。
treap
treap是一种平衡树，除了平衡树的特点以外，treap中每个结点还有一个随机的额外权值、
treap根据额外权值满足堆的性质，即每个结点左右儿子的额外权值都大于该节点。
在随机权值互不相等的情况下，权值与treap是一一对应的。
由于堆的权值是随机的，所以树的期望深度为logn。
我们主要运用旋转(rotate)来维护平衡树的性质。
Markdown
转一下，然后把右儿子换一下
容易发现旋转操作并不会改变平衡树的性质，只会让两个元素上下位置交换，所以插入点的时候，只要在treap中找到恰好能插入这个点的位置，将这个点插入，再通过rotate操作将他向上移动，直到满足堆的性质。（转来转去让它的左儿子比它小，右儿子比它大）
在删除点的时候，用rotate操作把当前点转移到叶子节点，删掉就行啦
单次操作O（logn）
void right_rotate(int p)//右旋
{
int q=dad[p],s=dad[q];
int b=rs[p];
ls[q]=b;
dad[b]=q;
dad[q]=p;
dad[p]=s;
rs[p]=q;
if(ls[s]==q)ls[s]=p;
else rs[s]=p;
}
void left_rotate(int p)//左旋
{
int q=dad[p];
int s=dad[q];
int t=rs[p];
dad[p]=s;
dad[q]=p;
dad[t]=q;
ls[q]=t;
rs[p]=q;
if(ls[s]==q)
ls[s]=p;
else
rs[s]=p;
}
无DAD版
void left_rotate (int &q,int p){
rs[q]=ls[p];
ls[p]=q;
q=p;
}
void right_rotate (int &q,int p){
ls[q]=rs[p];
rs[p]=q;
q=p;
}
void add(int x,int &cur)
{
if(!cur)
{
cur=++cnt;//cur表示一个节点的编号
v[cnt]=x;
R[cnt]=rand();
return ;//新建节点
}
if(x>V[cur])
{
add(x,rs[cur]);//向右儿子找
if(R[rs[cur]]<R[cur]) left_rotate(rs[cur]);//旋转
}
else
{
add(x,ls[cur]);//向左儿子找
if(R[ls[cur]]<R[cur]) right_rotate(ls[cur]);//旋转
}
}
void del(int x,int &cur)
{
if(V[cur]==x)
{
if(!ls[cur]||!rs[ur])
{
cur=ls[cur]|rs[cur];
return;
}
if(R[ls[cur]]>R[rs[cur]])
{
left_rotate(cur,rs[cur]);
del(x,ls[cur]);
}
else
{
right_rotate(cur,ls[cur]);
del(x,rs[cur]);
}
}
else if(x<V[cur]) del(x,ls[cur]);
else del(x,rs[cur]);
}
add(x,root);
}
splay
splay也是一种平衡树，满足平衡树的所有性质。
它不能可持久化。
与treap不同的是，splay依赖双旋均摊来保证复杂度。
splay的基本操作函数splay(X)表示将x旋转到根。//只要x不是根就不断splay
splay函数中的旋转根据三种不同的情况进行分类讨论：
P：x的父亲
当P为根节点时：zip step操作：
1）当x为p的左儿子时，对x右旋；
2）当x为p的右儿子时，对x左旋。
当P不是根节点，且x和p同为左儿子或右儿子时进行zig-zig操作。
1）当x和p同为左孩子时，依次将p和x右旋；
2）当x和p同为右孩子时，依次将p和x左旋。
当p不是根节点，且x与p不同为左孩子或者右孩子时，进行zig-zag操作。
1）当p为左孩子，X为右孩子的时候，将x左旋以后再右旋。
2）当p为右孩子，X为左孩子的时候，将x右旋后再左旋。
Markdown
void splay(int x)
{
st[t=1]=x;
for(int y=x;!is_root(y);st[++t]=y=dad[y]);
for(;t;t–) if(rev[st[t]]) reverse(st[t]);
for(;!is_root(x);rotate(x))
if(!is_root(dad[x]))
s[0][dad[x]]==x^s[0][dad[dad[x]]]==dad[x]?rotate(x):rotate(dad[x]);
update(x);
}
int find_max(int cur)
{
for(;s[1][cur];cur=s[1][cur]);
return cur;
}
void combine(int cur,int cur1)
{
cur=find_max(cur);
splay(cur);
rs[cur]=cur1;
}
fhp-treap被老师吃辣！
替罪羊树：局部重构【第二快的平衡树】
最快的是RBT（红黑树）
朝鲜树：隔一段时间把树拍成一条链，然后再重构
BZOJ3224 普通平衡树
需要满足插入元素的操作，删除指定元素的操作，查询某数序号的操作，查询排名为x的数（维护子树大小），求x前驱的操作
【线段树多好】
BZOJ3223 文艺平衡树
维护有序数列，能够翻转区间。
利用splay,每次操作将区间[l,r]左侧点l-1旋转到根，将区间右端点r+1旋转到根的右儿子，这时区间对应的就是根右儿子的左儿子。给节点打上翻转标记即可。
//如果使用fhp-treap，我们可以先将区间通过两次split分离出来，打上标记再merge回去。
线段树
//偷偷告诉你们 指针写线段树 超~ ~ ~ ~ ~爽【其实没什么卵用】
//没有lazytag的线段树，和咸段树有什么区别……？
#include <bits/stdc++.h>
using namespace std;
void pushdown(int cur,int x)
{
cov[cur<<1]=cov[cur<<1|1]=cov[cur];
sum[cur<<1]+=cov[cur](x+1>>1);
sum[cur<<1|1]+=cov[cur](x>>1);
cov[cur]=0;
}
void update(int cur)
{
sum[cur]=sum[cur<<1]+sumpcur<<1|1];
}
void add(int l,int r,int L,int R,int x,int cur)//加点
{
if(L=<l&&R>=r)
{
cov[cur]+=x;//cov就是lazytag
sum[cur]+=(r-l+1)*x;
return x;
}
int mid=l+r>>1;
if(L<=mid)add(l,mid,L,R,x,cur<<1);
if(R>mid)add(mid+1,r,L,R,x,cur<<1|1);
}
int query(int l,int r,int L,int R,int cur)
{
if(L<=l&&R>=r) return sum[cur];
if(cov[cur]) pushdown(cur,r-l+1);
int mid=l+r>>1,ans=0;
if(L<=mid)ans+=query(l,mid,L,R,cur<<1);
if(R>mid)ans+=query(mid+1,r,L,R,cur<<1|1);
return ans;
}