6树状数组学习笔记
【6】树状数组学习笔记
前言
树状数组是我学的第一个高级数据结构，属于
log \log
lo g 级数据结构。
其实现在一般不会单独考察数据结构，主要是其在其他算法（如贪心，DP）中起到优化作用。
**长文警告：本文一共
995 995
995 行，请合理安排阅读时间。**
lowbit函数
lowbit函数用于求解一个数二进制位最右边的
1 1
1 表示的权值，可以使用下面函数计算。
int lowbit(int x)
{
return (x&(-x));
}举个例子：
x
1010100100 ;;x=1010100100
x
=
1010100100
− x
0101011100 -x=0101011100
−
x
=
0101011100
x & ( − x )
0000000100
4 x&(-x)=0000000100=4
x
&
(
−
x
)
=
0000000100
=
4
树状数组本质上是一个数组，属于 线性 数据结构。树状数组中，把数按照其
l o w b i t lowbit
l
o
w
bi
t 值进行 分层 ，分层虽然没有明显的操作与现象，但导致画出来的层次像树一样，所以叫做 树状数组 。
单点修改+区间查询
树状数组支持 单点修改 ， 区间查询 （一般是 求和 ）。
对于
c c
c 数组的定义（初始化）：
c k
∑ i
k − l o w b i t ( k ) + 1 k a i c_k=\sum_{i=k-lowbit(k)+1}^{k}a_i
c
k
=
i
=
k
−
l
o
w
bi
t
(
k
)
1
∑
k
a
i
原理类似于倍增，把原数组下标
k k
k 按照二进制每位进行拆分，通过每个二进制位求出一段区间的和，最后加和得到区间前缀和。
注意：下标从
1 1
1 开始存储。
查询前缀和
使用
l o w b i t lowbit
l
o
w
bi
t 求出下标最右边二进制位为
1 1
1 的数位表示的值，然后
c c
c 数组对应元素累加到结果，再减去这个
l o w b i t lowbit
l
o
w
bi
t 值，使之后可以求出下标第二右边二进制位为
1 1
1 的数位表示的值。重复这个过程，直到下标为
0 0
0 。
举个例子：
求
a a
a 中
[ 1 , 6 ] [1,6]
[
1
,
6
] 的前缀和。
首先，因为
6
110 , l o w b i t ( 6 )
2 6=110,lowbit(6)=2
6
=
110
,
l
o
w
bi
t
(
6
)
=
2 ，所以
c 6
a 5 + a 6 c_6=a_5+a_6
c
6
=
a
5
a
6
。
然后，将最后一位的
1 1
1 减掉，得到
4
100 , l o w b i t ( 4 )
4 4=100,lowbit(4)=4
4
=
100
,
l
o
w
bi
t
(
4
)
=
4 ，所以
c 4
a 1 + a 2 + a 3 + a 4 c_4=a_1+a_2+a_3+a_4
c
4
=
a
1
a
2
a
3
a
4
。
最后，
c 4 + c 6
a 1 + a 2 + a 3 + a 4 + a 5 + a 6 c_4+c_6=a_1+a_2+a_3+a_4+a_5+a_6
c
4
c
6
=
a
1
a
2
a
3
a
4
a
5
a
6
，也就是
a a
a 中
[ 1 , 6 ] [1,6]
[
1
,
6
] 的前缀和。
正确性证明：
设原下标为
k k
k ，由
l o w b i t lowbit
l
o
w
bi
t 和
c c
c 数组的定义得求出
[ k − l o w b i t ( k ) + 1 , k ] [k-lowbit(k)+1,k]
[
k
−
l
o
w
bi
t
(
k
)
1
,
k
] 的和。设减去
l o w b i t ( k ) lowbit(k)
l
o
w
bi
t
(
k
) 得
l l
l ，求出
[ l − l o w b i t ( l ) + 1 , k − l o w b i t ( k ) ] [l-lowbit(l)+1,k-lowbit(k)]
[
l
−
l
o
w
bi
t
(
l
)
1
,
k
−
l
o
w
bi
t
(
k
)] 。观察得这两个区间是相接且不交叉的，可以合并为
[ l − l o w b i t ( l ) + 1 , k ] [l-lowbit(l)+1,k]
[
l
−
l
o
w
bi
t
(
l
)
1
,
k
] ，这样递推下去。由于最后下标为
0 0
0 ，故一定可以合并成
[ 1 , k ] [1,k]
[
1
,
k
] 。证毕。
int getsum(int x)
{
int t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
)
单点修改
单点修改一个下标后，受影响的必然是减去
l o w b i t lowbit
l
o
w
bi
t 后是这个下标，所以可以把
l o w b i t lowbit
l
o
w
bi
t 加回来，同时把
c c
c 数组增加。当然，如果超过了数组元素个数
n n
n 就没必要再加了。
void add(int x,int d)
{
while(x<=n)c[x]+=d,x+=lowbit(x);
}时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
)
初始化
不需要按照
c c
c 数组的定义来，可以把每一个数都进行一次单点修改操作。
void init()
{
for(int i=1;i<=n;i++)add(i,a[i]);
}时间复杂度：
O ( n log n ) O(n\log n)
O
(
n
lo g
n
)
区间求和
使用查询前缀和查询出前缀和，然后相减就是区间的和。
int ask(int x,int y)
{
return getsum(y)-getsum(x-1);
}时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
)
单点修改+区间查询例题
例题
1 1
1 ：
单点修改+区间查询模板题，不多赘述。
#include <bits/stdc++.h>
using namespace std;
int n,m,a[600000],c[600000];
int lowbit(int x)
{
return (x&(-x));
}
void add(int x,int d)
{
while(x<=n)c[x]+=d,x+=lowbit(x);
}
void init()
{
for(int i=1;i<=n;i++)add(i,a[i]);
}
int getsum(int x)
{
int t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}
int ask(int x,int y)
{
return getsum(y)-getsum(x-1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
init();
for(int i=0;i<m;i++)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1)add(x,y);
else if(op==2)printf("%d\n",ask(x,y));
}
return 0;
}例题
2 2
2 ：
类似例题
1 1
1 ，但是不用初始化，注意字符的输入。
#include <bits/stdc++.h>
using namespace std;
long long n,m,a[600000],c[600000];
long long lowbit(long long x)
{
return (x&(-x));
}
void add(long long x,long long d)
{
while(x<=n)c[x]+=d,x+=lowbit(x);
}
long long getsum(long long x)
{
long long t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}
long long ask(long long x,long long y)
{
return getsum(y)-getsum(x-1);
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
char op;
int x,y;
cin>>op>>x>>y;
if(op=='x')add(x,y);
else if(op=='y')printf("%lld\n",ask(x,y));
}
return 0;
}例题
3 3
3 ：
树上树状数组。
由于每次每头牛走完之后会单点修改一个值，而放慢速度的次数又取决于从根到目标节点的区间和，自然联想到树状数组。
首先预处理出每个节点的层次，一方面方便遍历树，另一方面方便树上树状数组。
对于单点修改的操作，考虑预处理出修改每个节点之后会影响的点，可以通过先搜索层次深的节点，搜索更浅的节点时记忆化，做到将近
O ( n log n ) O(n\log n)
O
(
n
lo g
n
) 的复杂度。
对于区间查询的操作，考虑预处理出查询每个节点之前会计算的点，可以通过先搜索层次浅的节点，搜索更深的节点时记忆化，同样做到将近
O ( n log n ) O(n\log n)
O
(
n
lo g
n
) 的复杂度。
然后，由于已经预处理了每个点的影响与计算，所以树状数组操作时只需要遍历这些预处理的记录就行了。
注意一定要记忆化，否则很容易退化回
O ( n 2 ) O(n^2)
O
(
n
2
) 。
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
struct edge
{
int to,next;
}e[300000];
struct order
{
int p,c;
}xu[100001];
struct node
{
int b;
vector<int>low;
vector<int>high;
}retree[100001];
int n,h[100001],tol=0,c[100001],book[100001];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
bool cmp(struct order a,struct order b)
{
return a.c>b.c;
}
void add_edge(int u,int v)
{
e[++tol].next=h[u];
e[tol].to=v;
h[u]=tol;
}
void dfs1(int root,int ce)
{
retree[root].b=ce;
for(register int i=h[root];i;i=e[i].next)
{
if(book[e[i].to])continue;
book[e[i].to]=1;
dfs1(e[i].to,ce+1);
}
}
void dfs2(int root,int from,int want)
{
if(retree[root].b==want)
{
int l=retree[root].low.size();
for(int i=0;i<l;i++)retree[from].low.push_back(retree[root].low[i]);
return;
}
if(want>n)return;
for(register int i=h[root];i;i=e[i].next)
{
if(retree[e[i].to].b<=retree[root].b)continue;
dfs2(e[i].to,from,want);
}
}
void dfs3(int root,int from,int want)
{
if(retree[root].b==want)
{
int l=retree[root].high.size();
for(int i=0;i<l;i++)retree[from].high.push_back(retree[root].high[i]);
want-=lowbit(want);
return;
}
if(want<=0)return;
for(register int i=h[root];i;i=e[i].next)
{
if(retree[e[i].to].b>=retree[root].b)continue;
dfs3(e[i].to,from,want);
}
}
void add(int x)
{
int l=retree[x].low.size();
for(register int i=0;i<l;i++)c[retree[x].low[i]]++;
}
int query(int x)
{
int t=0,l=retree[x].high.size();
for(register int i=0;i<l;i++)
t+=c[retree[x].high[i]];
return t;
}
int main()
{
n=read();
for(register int i=0;i<n-1;i++)
{
int u,v;
u=read();v=read();
add_edge(u,v);
add_edge(v,u);
}
for(register int i=1;i<=n;i++)
{
retree[i].low.push_back(i);
retree[i].high.push_back(i);
}
book[1]=1;
dfs1(1,1);
for(register int i=1;i<=n;i++)
xu[i].p=i,xu[i].c=retree[i].b;
sort(xu+1,xu+n+1,cmp);
for(register int i=1;i<=n;i++)dfs2(xu[i].p,xu[i].p,retree[xu[i].p].b+lowbit(retree[xu[i].p].b));
for(register int i=n;i>=1;i--)dfs3(xu[i].p,xu[i].p,retree[xu[i].p].b-lowbit(retree[xu[i].p].b));
for(register int i=1;i<=n;i++)
{
int p;
p=read();
printf("%d\n",query(p));
add(p);
}
return 0;
}当然，每次修改时计算也是可以的，而且可以大大减少码量，这里不多赘述。
例题
4 4
4 ：
由于权值值域很小（
c ≤ 100 c\le100
c
≤
100 ），可以对每一种权值建立一个二维树状数组，每次更新时单独更新。一个某种权值的格子会对这种权值的答案造成
1 1
1 的贡献，所以可以把每个这种权值的格子视为
1 1
1 ，其他的格子视为
0 0
0 。统计个数时加起来就行了。
操作
1 1
1 的处理：
首先，如果把
a a
a 修改成
b b
b ，那么会影响
a a
a 和
b b
b 两种权值的二维树状数组。可以把
a a
a 的树状数组影响到的值都加
1 1
1 ，而
b b
b 的树状数组影响到的值都减
1 1
1 ，从而达到修改的目的。
注意：
对于影响到的值，可以参考一维树状数组的解决方式。将横坐标与纵坐标分别加上其
l o w b i t lowbit
l
o
w
bi
t ，把原区间划分为四个小区间。
void add(int x,int y,int k,int s)
{
int i=x,j=y;
while(x<=n)
{
y=j;
while(y<=m)c[x][y][s]+=k,y+=lowbit(y);
x+=lowbit(x);
}
}
void insert()
{
int x=0,y=0,c=0;
scanf("%d%d%d",&x,&y,&c);
add(x,y,1,c);
add(x,y,-1,a[x][y]);
a[x][y]=c;
}操作
2 2
2 的处理：
设
s [ i ] [ j ] s[i][j]
s
[
i
]
[
j
] 表示二维右下点为
( i , j ) (i,j)
(
i
,
j
) 的矩形的前缀和，利用容斥原理得到矩形
( x 1 , y 1 , x 2 , y 2 ) (x_1,y_1,x_2,y_2)
(
x
1
,
y
1
,
x
2
,
y
2
) 的加和值为：
s [ x 2 ] [ y 2 ] − s [ x 1 − 1 ] [ y 2 ] − s [ x 2 ] [ y 1 − 1 ] + s [ x 1 − 1 ] [ y 1 − 1 ] s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]
s
[
x
2
]
[
y
2
]
−
s
[
x
1
−
1
]
[
y
2
]
−
s
[
x
2
]
[
y
1
−
1
]
s
[
x
1
−
1
]
[
y
1
−
1
]
对于前缀和的处理，可以参考一维树状数组的解决方式。将横坐标与纵坐标分别减去其
l o w b i t lowbit
l
o
w
bi
t ，把原区间划分为四个小区间。
int getsum(int x,int y,int k)
{
int t=0,i=x,j=y;
while(x>0)
{
y=j;
while(y>0)t+=c[x][y][k],y-=lowbit(y);
x-=lowbit(x);
}
return t;
}
int query()
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
return (getsum(x2,y2,c)-getsum(x1-1,y2,c)-getsum(x2,y1-1,c)+getsum(x1-1,y1-1,c));
}最后，把这些操作拼起来，再加上输入输出与初始化即可。
#include <bits/stdc++.h>
using namespace std;
int n,m,q,a[301][301],c[301][301][101],op;
int lowbit(int x)
{
return (x&(-x));
}
void add(int x,int y,int k,int s)
{
int i=x,j=y;
while(x<=n)
{
y=j;
while(y<=m)c[x][y][s]+=k,y+=lowbit(y);
x+=lowbit(x);
}
}
void insert()
{
int x=0,y=0,c=0;
scanf("%d%d%d",&x,&y,&c);
add(x,y,1,c);
add(x,y,-1,a[x][y]);
a[x][y]=c;
}
int getsum(int x,int y,int k)
{
int t=0,i=x,j=y;
while(x>0)
{
y=j;
while(y>0)t+=c[x][y][k],y-=lowbit(y);
x-=lowbit(x);
}
return t;
}
int query()
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
return (getsum(x2,y2,c)-getsum(x1-1,y2,c)-getsum(x2,y1-1,c)+getsum(x1-1,y1-1,c));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
add(i,j,1,a[i][j]);
scanf("%d",&q);
for(int i=0;i<q;i++)
{
scanf("%d",&op);
if(op==1)insert();
else if(op==2)printf("%d\n",query());
}
return 0;
}区间修改+单点查询
树状数组支持 单点查询 ， 区间修改 （一般是 求和 ）。
单点修改，区间查询使用的是前缀和思想，把它反过来，变成差分思想，就能够实现单点查询，区间修改。
首先建立一个差分数组，其中每个值定义为：
b i
a i ( i
1 ) b_i=a_i(i=1)
b
i
=
a
i
(
i
=
1
)
b i
a i − a i − 1 ( i ≠ 1 ) b_i=a_i-a_{i-1}(i\neq1)
b
i
=
a
i
−
a
i
−
1
(
i
=
1
)
之后，在差分数组上建立树状数组。
单点查询
同单点修改，区间查询的查询前缀和。
因为由差分数组的定义，可以知道差分数组前
i i
i 项的和为：
b i + b i − 1 ⋯ + b 2 + b 1
a i − a i − 1 + a i − 1 − a i − 2 ⋯ + a 2 − a 1 + a 1
a i \begin{aligned} b_i+b_{i-1}\dots+b_2+b_1 = a_i&-a_{i-1}+a_{i-1}-a_{i-2}\dots+a_{2}-a_{1}+a_{1}\=a_i\end{aligned}
b
i
b
i
−
1
⋯
b
2
b
1
=
a
i
=
a
i
−
a
i
−
1
a
i
−
1
−
a
i
−
2
⋯
a
2
−
a
1
a
1
所以，可以直接在差分数组上查询前
i i
i 项的前缀和，就是
a i a_i
a
i
的值。
int getsum(int x)
{
int t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
)
区间修改
对于
[ l , r ] [l,r]
[
l
,
r
] 区间增加
k k
k 的修改，可以把位置分为一下几类：
1 1
1 ：
l < i ≤ r l\lt i\le r
l
<
i
≤
r
b i
b i + k − ( b i − 1 + k )
b i − b i − 1 b_i=b_i+k-(b_{i-1}+k)=b_i-b_{i-1}
b
i
=
b
i
k
−
(
b
i
−
1
k
)
=
b
i
−
b
i
−
1
没有变化，无需修改。
2 2
2 ：
i
l i=l
i
=
l
b i
b i + k − b i − 1
b i − b i − 1 + k b_i=b_i+k-b_{i-1}=b_i-b_{i-1}+k
b
i
=
b
i
k
−
b
i
−
1
=
b
i
−
b
i
−
1
k
按照之前的修改操作将第
l l
l 项
k +k
k 即可。
3 3
3 ：
i
r + 1 i=r+1
i
=
r
1
b i
b i − ( b i − 1 + k )
b i − b i − 1 − k b_i=b_i-(b_{i-1}+k)=b_i-b_{i-1}-k
b
i
=
b
i
−
(
b
i
−
1
k
)
=
b
i
−
b
i
−
1
−
k
按照之前的修改操作将第
r + 1 r+1
r
1 项
− k -k
−
k 即可。
void add(int x,int d)
{
while(x<=n)c[x]+=d,x+=lowbit(x);
}
void pluss()
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
add(x,k);add(y+1,-k);
}时间复杂度：
O ( log n ) O(\log n)
O
(
lo g
n
)
初始化
在差分数组上建立树状数组。
void init()
{
for(int i=1;i<=n;i++)add(i,b[i]);
}时间复杂度：
O ( n log n ) O(n\log n)
O
(
n
lo g
n
)
区间修改+单点查询例题
例题
5 5
5 ：
区间修改+单点查询模板题，不多赘述。
#include <bits/stdc++.h>
using namespace std;
int n,m,a[600000],b[600000],c[600000];
int lowbit(int x)
{
return (x&(-x));
}
void add(int x,int k)
{
while(x<=n)c[x]+=k,x+=lowbit(x);
}
void init()
{
for(int i=1;i<=n;i++)add(i,b[i]);
}
int getsum(int x)
{
int ans=0;
while(x>0)ans+=c[x],x-=lowbit(x);
return ans;
}
void pluss()
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
add(x,k);add(y+1,-k);
}
int ask()
{
int x;
scanf("%d",&x);
return getsum(x);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
init();
for(int i=1;i<=m;i++)
{
int op;
scanf("%d",&op);
if(op==1)pluss();
else if(op==2)printf("%d\n",ask());
}
return 0;
}例题
6 6
6 ：
同例题
5 5
5 ，不用初始化。
对于数字反转，可以修改时直接将数字加
1 1
1 ，查询时利用对
2 2
2 取模的周期性来解决。
#include <bits/stdc++.h>
using namespace std;
int n,m,b[600000],c[600000];
int lowbit(int x)
{
return (x&(-x));
}
void add(int x,int k)
{
while(x<=n)c[x]+=k,x+=lowbit(x);
}
int getsum(int x)
{
int ans=0;
while(x>0)ans+=c[x],x-=lowbit(x);
return ans;
}
void pluss()
{
int x,y,k=1;
scanf("%d%d",&x,&y);
add(x,k);add(y+1,-k);
}
int ask()
{
int x;
scanf("%d",&x);
return (getsum(x)+2)%2;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int op;
scanf("%d",&op);
if(op==1)pluss();
else if(op==2)printf("%d\n",ask());
}
return 0;
}树状数组求逆序对
一般来说，可以使用 归并排序 来求一个序列中的逆序对数。但是，树状数组也可以完成。
其中步骤如下：
1 1
1 ：将数组离散化，映射到
1 ∼ n 1\sim n
1
∼
n 。
教练推荐的离散化博客：
2 2
2 ：建立一个树状数组，
c i c_i
c
i
表示离散化后数字
i i
i 出现的次数。
3 3
3 ：从左到右依次遍历数组，设这个
a i a_i
a
i
为
k k
k 每次修改对应
c k c_k
c
k
，进行一次
1 +1
1 。然后根据数组有序时的要求是升序还是降序，查询
[ k + 1 , n ] [k+1,n]
[
k
1
,
n
] 或
[ 1 , k − 1 ] [1,k-1]
[
1
,
k
−
1
] 的区间和，累加进
a n s ans
an
s 。
4 4
4 ：结束，输出
a n s ans
an
s 。
树状数组求逆序对用到的是 单点修改+区间查询 的树状数组。
树状数组求逆序对例题
例题
7 7
7 ：
求逆序对数板子题，可以归并排序，亦可树状数组，这里使用树状数组，不多赘述。
#include <bits/stdc++.h>
using namespace std;
struct node
{
long long x,y;
}a[600000];
long long n,m,ans=0,b[600000],c[600000];
bool cmp(struct node a,struct node b)
{
return a.y<b.y;
}
long long lowbit(long long x)
{
return (x&(-x));
}
void add(long long x,long long d)
{
while(x<=n)c[x]+=d,x+=lowbit(x);
}
void init()
{
sort(a+1,a+n+1,cmp);
b[a[1].x]=++m;
for(long long i=2;i<=n;i++)
if(a[i].y!=a[i-1].y)b[a[i].x]=++m;
else b[a[i].x]=m;
}
long long getsum(long long x)
{
long long t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<=n;i++)
{
scanf("%lld",&a[i].y);
a[i].x=i;
}
init();
for(long long i=1;i<=n;i++)
{
add(b[i],1);
ans+=(i-getsum(b[i]));
}
printf("%lld",ans);
return 0;
}例题
8 8
8 ：
实质就是求一个数组的逆序对数，推导过程可以看 杂项部分
3.2 3.2
3.2 的证明部分。
#include <bits/stdc++.h>
using namespace std;
struct node
{
long long x,y;
}a[600000];
long long n,m,ans=0,b[600000],c[600000];
bool cmp(struct node a,struct node b)
{
return a.y<b.y;
}
long long lowbit(long long x)
{
return (x&(-x));
}
void add(long long x,long long d)
{
while(x<=n)c[x]+=d,x+=lowbit(x);
}
void init()
{
sort(a+1,a+n+1,cmp);
b[a[1].x]=++m;
for(long long i=2;i<=n;i++)
if(a[i].y!=a[i-1].y)b[a[i].x]=++m;
else b[a[i].x]=m;
}
long long getsum(long long x)
{
long long t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<=n;i++)
{
scanf("%lld",&a[i].y);
a[i].x=i;
}
init();
for(long long i=1;i<=n;i++)
{
add(b[i],1);
ans+=(i-getsum(b[i]));
}
printf("%lld",ans);
return 0;
}例题
9 9
9 ：
首先，为了计算方便，可以以中间那个数，也就是
a j a_j
a
j
为基准。设在在这个数之前有
n n
n 个数比它小，在这个数之后有
m m
m
个数比它大，那么由于前后各自任选一个就能构成一组
thair
，根据乘法原理得到
a n s ans
an
s 应该累加
n × m n\times m
n
×
m 。
我们可以进行两次树状数组求逆序对：第一次求某个数之前比它小的数的个数，第二次反转序列，求某个数之后比它大的数的个数。
由于
a i a_i
a
i
的范围很小，所以不用离散化，但是 。
#include <bits/stdc++.h>
using namespace std;
long long n,ans=0,maxn=0,a[300000],c[300000],ls[300000],rb[300000];
long long lowbit(long long x)
{
return (x&(-x));
}
void add(long long x,long long d)
{
while(x<=maxn)c[x]+=d,x+=lowbit(x);
}
long long getsum(long long x)
{
long long t=0;
while(x>0)t+=c[x],x-=lowbit(x);
return t;
}
int main()
{
scanf("%lld",&n);
for(long long i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
maxn=max(maxn,a[i]);
}
for(long long i=1;i<=n;i++)
{
add(a[i],1);
ls[i]=getsum(a[i]-1);
}
memset(c,0,sizeof(c));
for(long long i=n;i>=1;i--)
{
add(a[i],1);
rb[i]=getsum(maxn)-getsum(a[i]);
}
for(long long i=1;i<=n;i++)
ans+=ls[i]*rb[i];
printf("%lld\n",ans);
return 0;
}例题
10 10
10 ：
排序题目的巅峰。
首先，由于距离是两数之差的平方，有一个显然的贪心：把两个数组从小到大排序，同一位置的数互相对应，此时距离最小。交换两数后，由于平方的影响，绝对值之差会较大，导致距离也较大，证明了贪心的正确性。
然后，将
a a
a 数组的每个数与
b b
b 数组建立映射关系，同时进行离散化。可以记录下数组
a a
a 中每个数字排序前的位置，再以排序后其对应的
b b
b 数组的元素的位置作为关键字进行离散化。这样相当于数组中记录的是在不改变
b b
b 数组的情况下，每个数组元素在距离最小情况下的排名。
由于数组记录的是排名，那么最小情况必然是一个单升不降的序列。此时的序列是一个乱序序列，要求最小化将这个序列排好序的相邻两数交换次数。这点就很像例题
8 8
8 ，实质就是求一个数组的逆序对数，树状数组求解即可，推导过程可以看 杂项部分
3.2 3.2
3.2 的证明部分。
由于每次交换，逆序对数量要么
1 +1
1 ，要么
− 1 -1
−
1 ，两个序列地位相同，可以只变换一个序列，最终最优解不受影响，再次保证了算法的正确性。
#include <bits/stdc++.h>
const int MOD=100000000-3;
using namespace std;
struct node
{
int x,v;
}a[200000],b[200000];
long long n,m=1,ans,c[200000],d[200000];
bool cmp(struct node a,struct node b)
{
return a.v<b.v;
}
long long lowbit(long long x)
{
return (x&(-x));
}
void add(long long x,long long k)
{
while(x<=m)c[x]+=k,x+=lowbit(x);
}
long long getsum(long long x)
{
long long ans=0;
while(x>0)ans+=c[x],x-=lowbit(x);
return ans;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].v);
a[i].x=i;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&b[i].v);
b[i].x=i;
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(i!=1&&a[i].v!=a[i-1].v)m++;
d[a[i].x]=b[i].x;
}
for(int i=1;i<=n;i++)
{
add(d[i],1);
ans+=((getsum(m)%MOD-getsum(d[i])%MOD)+MOD)%MOD;
ans%=MOD;
}
printf("%lld\n",ans%MOD);
return 0;
}后记
树状数组讲了两个星期，可见其内容之多，共
995 995
995 行。
数据结构果然毒瘤啊qaq