并查集
并查集，是一种树形数据结构，用于维护不相交的集合。
基本原理
每个集合用一棵树来表示，树根的编号就是整个集合的编号。
每个节点存储了它的父节点。
模板题（AcWing.836）
一共有 n 个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
M a b，将编号为 \(a\) 和 \(b\) 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 \(a\) 和 \(b\) 的两个数是否在同一个集合中；
并查集实现
思路
维护一个数组 \(p\) 来表示每个节点的父节点。
判断树根
显然，如果一个节点的父节点是它本身，那它就是根节点。
代码：
inline bool is_root(ll x)
{
if(p[x]==x) return 1;
else return 0;
}
这个在本题中用不着。
合并集合
可以发现，如果要将 \(a\) 并入 \(b\) （其实等同于将 \(b\) 并入 \(a\) ），仅需在 \(a\) 的根节点和 \(b\) 的根节点间加入一条边。（原创图）
Q：那如果题目数据特别毒瘤，不间断地合并很多集合怎么办？那不就被卡成 \(\operatorname{O(n)}\) 了吗？
A：路径压缩的 find() 只会跑一遍 \(\operatorname{O(n)}\) ，就会重新变为 \(\operatorname{O(1)}\) 。
代码：
p[find(a)]=find(b);
求 \(x\) 的集合编号
递归查找。
inline ll find(ll x)
{
if(p[x]!=x) p[x]=find(p[x]);//不断查找父节点，直到找到根节点
return p[x];
}
以上代码添加了路径压缩，也就是 p[x]=find(p[x]) 在找到父节点的同时顺带更新了 p[x] 的值。
图示（原创图）：
相当于你问你爸爸你的祖先是谁，你爸爸也不知道，爸爸就去问爷爷，然后你的爷爷也不知道，爷爷就去问你的太爷爷，你的太爷爷年纪太大了，啥也不记得，就去问你的祖先。
代码
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 100005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return (f==1)?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll n=read(),m=read(),p[N];
inline ll find(ll x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
for(ll i=1;i<=n;i++) p[i]=i;
while(m--)
{
char op[2];ll a,b;
scanf("%s%lld%lld",op,&a,&b);//这里用 read() 会死
if(op[0]=='M') p[find(a)]=find(b);
else
{
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
}
return 0;
}
树状数组
树状数组（Binary Indexed Tree，BIT），即二叉索引树，适用于一些区间修改操作。
树状数组和线段树可是亲兄弟了，但他俩毕竟还有一些区别：树状数组能有的操作，线段树一定有；线段树有的操作，树状数组不一定有。
树状数组和线段树的复杂度同级，单次操作都是 \(\operatorname{O(log_2n)}\) ，但树状数组常数更小，速度比线段树快得多，代码简单清晰，因此，能用树状数组时要尽量用。
不过，树状数组不像线段树是那样要用 biuld() 建出一棵树，它是用数组模拟树形结构。
图解
下图解释了树状数组的存储模式，\(a\) 数组负责存储元素真正的值，\(c\) 数组就是树状数组，负责管理 \(a\) 数组， \(c_i\) 出发的箭头指向其管理的元素。比如要进行区间求和操作， \(c_i\) 就表示它出发的箭头指向的所有元素之和。
这就是树状数组的存储方式。
重点——lowbit函数
\(C_1=A_1\)
\(C_2=A_1+A_2\)
\(C_3=A_3\)
\(C_4=A_1+A_2+A_3+A_4\)
\(C_5=A_5\)
\(C_6=A_5+A_6\)
\(C_7=A_7\)
\(C_8=A_1+A_2+A_3+A_4+A_5+A_6+A_7+A_8\)
\(......\)
可以发现，这颗树是有规律的。
设k为i的二进制中从最低位到高位连续零的长度，有：
\(c_i=a_{i-2^k+1}+a_{i-2^k+2}+...+a_i\)
求和：根据上面的式子，可得：
\(sum_i=c_i+c+c_{(i-2^{k1})-2^{k2}}+...\)
\(sum_i=2^k\)
可得：
\(2^k=i\) & \(i^{i-1}\)
\(2^k=i\) & \(-i\)
这就是 lowbit() 函数，它可以找到 \(x\) 在二进制上的第一个 1 的位置。
lowbit函数代码
ll lowbit(ll x){return x&-x;}
一维树状数组
在 \(c\) 数组中更新 \(a\) 数组的元素
树状数组的重点就是利用二进制的变化，动态地更新树状数组。
下图解释了树状数组的元素更新原理。
由图可知， \(a_i\) 如果要更新，那么首先管理它的直接上级 \(c_i\) 就需要最先更新，然后利用 lowbit() 找到 \(c_i\) 的父节点并更新，直到更新完所有的节点。
区间修改代码
写法1
void add(ll x,ll y)
{
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
}
写法2
void add(ll x,ll y)
{
for(ll i=x;i<=n;i+=lowbit(i))
c[i]+=y;
}
如何建出树状数组
如果你看懂了上面的内容，再稍加思考，就可以想到。
其实只要在输入时将 \(a_i\) 更新进去即可。
初始化代码
for(ll i=1;i<=n;i++)
{
a[i]=read();
add(i,a[i]);
}
如何查询区间和
请看下面一个例子：
如果你有几张钱币，分别是 1、2、4、8 元，那么你就可以凑出十五元以内的任何钱数，如：
\(1=1\)
\(2=2\)
\(3=2+1\)
\(4=4\)
\(5=4+1\)
\(6=4+2\)
\(7=4+2+1\)
\(8=8\)
\(9=8+1\)
\(10=8+2\)
\(11=8+2+1\)
\(12=8+4\)
\(13=8+4+1\)
\(14=8+4+2\)
\(15=8+4+2+1\)
同样的，利用 \(c\) 数组的不同组合，也可以求出任何的区间和。
区间求和的顺序与区间更新有点区别，区间更新的顺序是通过子节点一级级更新祖先，区间查询是从后往前用 lowbit() 找到要加的元素。
首先定义一个 \(ret\) 来存储区间和。
然后用 lowbit() 找到要加的元素并加上它。
区间求和代码
写法1
ll sum(ll x)
{
ll ret=0;
while(x)
{
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
写法2
ll sum(ll x)
{
ll ret=0;
for(ll i=x;i;i-=lowbit(x))
ret+=c[x];
return ret;
}
代码
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 500005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;static char c=getchar();
while(!isdigit(c)){if(c=='-') f=0;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}//卡常
cll n=read();
ll m=read(),c[N];
void add(ll i,ll x){while(i<=n) c[i]+=x,i+=(i&-i);}
ll answer(ll x)
{
rll ret=0;
while(x) ret+=c[x],x-=(x&-x);
return ret;
}//树状数组
int main()
{
for(rll i=1;i<=n;i++) add(i,read());
while(m--)
{
cll op=read(),l=read(),r=read();
if(op==1) add(l,r);
else write(answer(r)-answer(l-1)),putchar('\n');
}
return 0;
}
二维树状数组
模板题（luogu.P4054/AcWing.2369）
一个 \(n × m\) 的方格，初始时每个格子有一个整数权值。接下来每次有 2 种操作：
- 改变一个格子的权值
- 求一个子矩阵中某种特定权值出现的个数
思路
二维树状数组加一维就行，再多写一维 \(color\) ，表示权值。
代码
#include <bits/stdc++.h>
#define ll int
#define rll register ll
#define cll const ll
#define N 305
#define M 105
using namespace std;
inline ll read()
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}//卡常
cll n=read(),m=read();
ll q,a[N][N],c[N][N][M];
inline void add(ll x,ll y,ll k,ll color)
{
for(rll i=x;i<=n;i+=(i&-i))
for(rll j=y;j<=m;j+=(j&-j))
c[i][j][color]+=k;
}
inline ll answer(ll x,ll y,ll color)
{
rll ret=0;
for(rll i=x;i;i-=(i&-i))
for(rll j=y;j;j-=(j&-j))
ret+=c[i][j][color];
return ret;
}//二维树状数组
int main()
{
for(rll i=1;i<=n;i++)
for(rll j=1;j<=m;j++)
a[i][j]=read(),add(i,j,1,a[i][j]);
q=read();
while(q--)
{
cll op=read();
if(op==1)
{
cll x=read(),y=read(),c=read();
add(x,y,-1,a[x][y]);a[x][y]=c;add(x,y,1,a[x][y]);
}//修改，记得先减去之前的颜色
else
{
cll x1=read(),x2=read(),y1=read(),y2=read(),c=read();
cll num=answer(x2,y2,c),num2=answer(x1-1,y2,c);
cll num3=answer(x2,y1-1,c),num4=answer(x1-1,y1-1,c);
write(num-num2-num3+num4),putchar('\n');
}//查询区间和，二维差分
}
return 0;
}