树状数组与线段树简单讲解与习题
一. 树状数组
时间复杂度
O(longN)
实现的操作
1.单点修改
2.区间查询
进阶一点就是区间修改和单点查询，区间修改和区间查询了(运用了差分的思想，不进行介绍)
树状数组用c表示原数组用a表示
c[1]=a[1] c[2]=a[2]+c[1] c[3]=a[3] c[4]=a[4]+c[3]+c[2]
以此类推
三个操作
1. 寻找父节点(下方假设下标为x，寻找其父节点)即找自身的上一层
上面的2,3会找到4 。 4,6会找到8......
x=x+(x&-x);
我们一般将(x&-x)封装成一个函数lowbit
int lowbit(int x)
{
return x&-x;
}2. 查询前缀和
假设要找原数组x位置的前缀和
int query(int x)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
res+=tr[i];//假设tr为树状数组
return res;
}这个i-=lowbit(i)呢是可以找到前一个区间，我们通过观察他的一个特性--->二进制决定层数就可以发现一个规律(证明太过繁琐，简单解释一下)：
例如 i=5 ：i-(5&-5) 就是5-1 变成了4 正好是没有加进去的一个区间
i=10 :i-(10&-10)= 10-2 变成8 也正好是没有加进去的一个区间
i=8 时 i-(8&-8)=8-8 变成0 。8前面确实没有没加进去的区间了
3. 单表修改
假设让原数组的x下标加上一个v
void add(int x,int v)
{
//假设N为树状数组长度
for(int i=x;i<=N;i+=lowbit(i))
tr[i]+=v;//要给树状数组这个下标后并且在上层的都更新上
}有一个要注意的点：这个更新的长度一定是树状数组的长度否则可能会出错。
二. 线段树
线段树呢比树状数组万能一些消耗也大一些但整体时间复杂度仍然是 O(logN)
树状数组能解决的问题用线段树也都可以
线段树除了最后一层就是一个完全二叉树(有争议)
其节点都是结构体
struct Node
{
int l;
int r;
int xxx;//根据题目
}
四个操作(大体操作)
1. 用子节点信息来更新自身的信息
void pushup(int u)
{
//将u的值根据左孩子与右孩子更新
//假如这是记录区间最大值，tr为线段树数组
tr[u].xxx=max(tr[u*2].xxx,tr[u*2+1].xxx);
}2. 在一段区间上初始化线段树
//u是线段树的下标
void build(int u,int l,int r)
{
if(l==r)
//完全初始化线段树
else
{
tr[u]={l,r};//初始化线段树
int mid=l+r>>1;
build(u*2,l,mid);//类似归并排序和堆找孩子
build(u*2+1,mid+1,r);
pushup(u);//等上面递归走完更新这个位置
}
}
3. 查询
int query(int u,int l,int r)
{
int xxx=0;
if(tr[u].l>=l&&tr[u].r<=r)//确认此节点区间被要查的区间包住了
//操作....
else
{
int mid=tr[u].l+tr[u].r>>1;
if(mid>=l)//左边孩子是0到mid
{
//需要往左孩子区间递归
}
//mid<r，向下取整不可能==r
if(mid<r)//右边是mid+1到n
{
//需要往右孩子区间递归
}
return xxx;
}
}4.修改
void modify(int u,int x,int v)//例如修改使原数组x位置加上v
{
if(tr[u].l==tr[u].r)//找到这个坐标
tr[u].sum+=v;
else
{
int mid=tr[u].l+tr[u].r>>1;
//mid是tr[u].l+tr[u].r中间的坐标
if(x<=mid)//要修改的坐标继续去子节点寻找
modify(u*2,x,v);
else
modify(u*2+1,x,v);
pushup(u);//原数组加上v了，更新父节点
}
}三. 习题
1. 动态求连续区间和
acwing 1264
给定 nn 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b][a,b] 的连续和。
输入格式
第一行包含两个整数 nn 和 mm，分别表示数的个数和操作次数。
第二行包含 nn 个整数，表示完整数列。
接下来 mm 行，每行包含三个整数 k,a,bk,a,b （k=0k=0，表示求子数列[a,b][a,b]的和；k=1k=1，表示第 aa 个数加 bb）。
数列从 11 开始计数。
输出格式
输出若干行数字，表示 k=0k=0 时，对应的子数列 [a,b][a,b] 的连续和。
数据范围
1≤n≤1000001≤n≤100000,
1≤m≤1000001≤m≤100000，
1≤a≤b≤n1≤a≤b≤n,
数据保证在任何时候，数列中所有元素之和均在 int 范围内。
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例：
11
30
35(1)树状数组解法
这个题目直观的给出了我们要进行的操作：单表修改和区间查询，区间连续和只要在查询区间时计算即可。代码如下
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a,b,k;
// int t[100010];
int tree[100010];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int v)//在下标x处加上一个v
{
for(int i=x;i<=n;i+=lowbit(i))
tree[i]+=v;
}
int query(int x)//查询区间前缀和
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
res+=tree[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int res=0;
// scanf("%d",&t[i]);
scanf("%d",&res);
add(i,res);
// for(int s=t[i]-lowbit(t[i]);s<=t[i];s++)
// tree[i]+=s;
}
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&k,&a,&b);
if(k==0)//输出a到b前缀和
{
printf("%d\n",query(b)-query(a-1));
}
else if(k==1)//改变tree数组
{
add(a,b);
}
}
return 0;
}(2)线段树解法
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int k,a,b;
struct Node
{
int l;
int r;
int sum;
}tr[4*100010];
int w[100010];
int pushup(int u)//用子节点信息更新当前节点
{
tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;//用左右孩子节点值更新自身sum
}
void build(int u,int l,int r)//初始化线段树
{
if(l==r)
tr[u]={l,r,w[r]};
else
{
tr[u]={l,r};//初始化坐标
int mid=l+r>>1;
//查询子节点
build(u*2,l,mid);
build(u*2+1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x,int v)//修改使原数组位置x加上v
{
if(tr[u].l==tr[u].r)//找到这个坐标
tr[u].sum+=v;
else
{
int mid=tr[u].l+tr[u].r>>1;
//mid是tr[u].l+tr[u].r中间的坐标
if(x<=mid)//要修改的坐标继续去子节点寻找
modify(u*2,x,v);
else
modify(u*2+1,x,v);
pushup(u);
}
}
int query(int u,int l,int r)//查询l到r这个区间
{
if(tr[u].l>=l&&tr[u].r<=r)//当前区间已经被完全包住了
return tr[u].sum;
int mid=tr[u].l+tr[u].r>>1;
int sum=0;//计算综合
if(l<=mid) //看左边有没有重合的
sum+=query(u*2,l,r);
if(r>mid)//看右边
sum+=query(u*2+1,l,r);
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
build(1,1,n);//
while(m--)
{
scanf("%d%d%d",&k,&a,&b);
if(k==0)//求和
{
printf("%d\n", query(1,a,b));
}
else if(k==1)//a位置加上b
{
modify(1,a,b);
}
}
return 0;
}2. 数星星
acwing 1265
天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。
本题采用数学上的平面直角坐标系，即 xx 轴向右为正方向，yy 轴向上为正方向。
如果一个星星的左下方（包含正左和正下）有 kk 颗星星，就说这颗星星是 kk 级的。
例如，上图中星星 55 是 33 级的（1,2,41,2,4 在它左下），星星 2,42,4 是 11 级的。
例图中有 11 个 00 级，22 个 11 级，11 个 22 级，11 个 33 级的星星。
给定星星的位置，输出各级星星的数目。
换句话说，给定 NN 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。
输入格式
第一行一个整数 NN，表示星星的数目；
接下来 NN 行给出每颗星星的坐标，坐标用两个整数 x,yx,y 表示；
不会有星星重叠。星星按 yy 坐标增序给出，yy 坐标相同的按 xx 坐标增序给出。
输出格式
NN 行，每行一个整数，分别是 00 级，11 级，22 级，……，N−1N−1 级的星星的数目。
数据范围
1≤N≤150001≤N≤15000,
0≤x,y≤320000≤x,y≤32000
输入样例：
5
1 1
5 1
7 1
3 3
5 5
输出样例:
1
2
1
1
0题目分析
由于按y座标增序，y相同的按x座标增序，所以y一定只会增大所以我们只需要看x坐标处及其前面的星星个数(即前缀和)就相当于存了星星的等级。x轴靠后的(即自身后面的)是不会被统计的
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
int tr[32010];
int lowbit(int x)
{
return x&-x;
}
void add(int x)//x坐标处又出现了一个星星，说明此处与后面要更新星星的数量++
{
//树状数组范围应该是x的最大值
for(int i=x;i<=32010;i+=lowbit(i))
{
//以后不会出现在这个x下面的星星了
tr[i]++;//为什么是加1呢？ ：因为统计的是下标为x的星星数量，
}
}
int query(int x)//查询前缀和即这个星星是那个等级 的
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))//减到自己的子节点
res+=tr[i];
//看这个子节点有几个星星(即这个下标处有几个星星)，再看自己的子节点(一定是最下面那个星星的子节点)
return res;
}
int level[15010]={0};
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
//当前输入的y一定是最大值，我们只需要看横坐标有多少星星《当前这个x
int x,y;
scanf("%d%d",&x,&y);
x++;//树状数组标从1开始，所以x下标要统一的加上1
//必须先增加等级的星星数量，因为后面树状数组更新可能会造成破坏
level[query(x)]++;//这个等级星星数量增加，
add(x);
}
for(int i=0;i<n;i++)
{
printf("%d\n",level[i]);
}
return 0;
}当然也可以用线段树此处不写了。
3. 数列区间最大值
acwing 1270
输入一串数字，给你 MM 个询问，每次询问就给你两个数字 X,YX,Y，要求你说出 XX 到 YY 这段区间内的最大数。
输入格式
第一行两个整数 N,MN,M 表示数字的个数和要询问的次数；
接下来一行为 NN 个数；
接下来 MM 行，每行都有两个整数 X,YX,Y。
输出格式
输出共 MM 行，每行输出一个数。
数据范围
1≤N≤1051≤N≤105,
1≤M≤1061≤M≤106,
1≤X≤Y≤N1≤X≤Y≤N,
数列中的数字均不超过231−1231−1
输入样例：
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例：
5
8题目分析
与第一个不同，要求我们求区间最大数，我们只需要在结构体区间内维护所存储l到r区间的最大值即可
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct Node
{
int l;
int r;
ll maxs=-1e18;//初始最大值设置为-1e18
}tr[4*100010];
ll w[100010];
int m,n;
void pushup(int u)
{
//父节比较看两个孩子节点的最大值
tr[u].maxs=max(tr[u*2].maxs,tr[u*2+1].maxs);
}
void build(int u,int l,int r)
{
if(l==r)
tr[u]={l,r,max(tr[u].maxs,w[r])};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
pushup(u);
}
}
ll query(int u,int l,int r)//查询这个区间的最大值
{
if(tr[u].l>=l&&tr[u].r<=r)
return tr[u].maxs;
else
{
int mid=tr[u].l+tr[u].r>>1;
ll tmpmax=-1e18;
if(mid>=l)//左边孩子是0到mid
{
tmpmax=max(query(u*2,l,r),tmpmax);
}
//mid<r，向下取整不可能==r
if(mid<r)//右边是mid+1到n
{
tmpmax=max(query(u*2+1,l,r),tmpmax);
}
return tmpmax;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
build(1,1,n);//初始化数组
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",query(1,x,y));
}
return 0;
}4. 小朋友排队
acwing 1215
nn 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候，所有小朋友的不高兴程度都是 00。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 11，如果第二次要求他交换，则他的不高兴程度增加 22（即不高兴程度为 33），依次类推。当要求某个小朋友第 kk 次交换时，他的不高兴程度增加 kk。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
输入的第一行包含一个整数 nn，表示小朋友的个数。
第二行包含 nn 个整数 H1,H2,…,HnH1,H2,…,Hn，分别表示每个小朋友的身高。
输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
数据范围
1≤n≤1000001≤n≤100000,
0≤Hi≤10000000≤Hi≤1000000
输入样例：
3
3 2 1
输出样例：
9
样例解释
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
题目分析
由于只能跟位置相邻的交换，其实就是一个冒泡排序的过程，我们可以通过记录每个小朋友的(最小)交换次数来统计不高兴程度。冒泡排序我们都知道，实际上冒泡排序一个位置的移动次数就是这个位置前面有几个比他大的与后面有几个数比他小的。例如样例给的 3 2 1 。2要交换两次，因为前面有一个3比他大，后面有一个1比他小。
我们用树状数组来维护身高，这样前缀和就是身高比要查询的位置(身高)小的了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long tr[1000010];
long long h[100010];
long long w[1000010];
int n;
int lowbit(int x)
{
return x&-x;
}
void add(int x,int v)
{
for(int i=x;i<=1000010;i+=lowbit(i))//确保这个树状数组都被更新
tr[i]+=v;
}
int query(int x)//查询这个数组
{
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&h[i]);
h[i]++;//防止有0
}
for(int i=1;i<=n;i++)
{
add(h[i],1);
//查询比h[i]大的数有多少
w[i]=i-query(h[i]);
}
memset(tr,0,sizeof(tr));
//查比自己小的
for(int i=n;i>=1;i--)
{
add(h[i],1);
//不能将自己也计算进去
w[i]+=query(h[i]-1);
}
long long sum=0;
for(int i=1;i<=n;i++)
{
// cout<<w[i]<<" ";
sum+=(1+w[i])*w[i]/2;//计算等差数列
}
printf("%lld",sum);
return 0;
}我们要注意几个点，第一次计算完前面比自己大的个数后要清空树状数组。
第二次计算比自己小的数要小心不要把自己给计算出来
还有这个不高兴值是累加的，需要用等差数列公式计算。
5. 油漆面积
X星球的一批考古机器人正在一片废墟上考古。
该区域的地面坚硬如石、平整如镜。
管理人员为方便，建立了标准的直角坐标系。
每个机器人都各有特长、身怀绝技。
它们感兴趣的内容也不相同。
经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。
矩形的表示格式为 (x1,y1,x2,y2)(x1,y1,x2,y2)，代表矩形的两个对角点坐标。
为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。
小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。
其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。
注意，各个矩形间可能重叠。
输入格式
第一行，一个整数 nn，表示有多少个矩形。
接下来的 nn 行，每行有 44 个整数 x1,y1,x2,y2x1,y1,x2,y2，空格分开，表示矩形的两个对角顶点坐标。
输出格式
一行一个整数，表示矩形覆盖的总面积。
数据范围
1≤n≤100001≤n≤10000,
0≤x1,x2,y1,y2≤100000≤x1,x2,y1,y2≤10000
数据保证 x1<x2x1<x2 且 y1<y2y1<y2。
输入样例1：
3
1 5 10 10
3 1 20 20
2 7 15 17
输出样例1：
340
输入样例2：
3
5 2 10 6
2 7 12 10
8 1 15 15
输出样例2：
128题目分析
有多个矩阵并且可能重复，我们需要用扫描线法来做，简易图如下
(实际上一个扫描线上有几个矩形就用线段树计算几次)
我们将每个矩形的开始的x坐标与结束的x坐标存储起来(由于扫描线是竖着画的，也可以横着画这样记录的就不是x而是y，后面记录x)，用k进行标记(k==1表示开始，k==-1表示结束)还要把y1与y2也记录进去。还要进行一个函数重载以完成对x的排序
struct line
{
int x;
int y1;//主要维护y轴
int y2;
int k;//看这个矩形是否走完了
bool operator<(const struct line& t)
{
return x<t.x;
}
}li[2*10010];我们的线段树节点则是除了l和r外要维护两个分别是
cnt：记录节点区间被覆盖的次数，(被覆盖了才能用区间长度更新len值)
len：记录矩形的长度
线段树的各个操作
struct Node
{
int l;
int r;
int cnt;//节点区间被覆盖的次数
int len;//长度，每次都要更新实际上就是区间所包含的矩形长度
}tr[4*10000];
void pushup(int u)
{
if(tr[u].cnt>0)//被覆盖了，len就是区间长度
tr[u].len=tr[u].r-tr[u].l+1;//+1是因为这是区间不是一个点，1和2这个区间长度为2。2-1+1=2
else if(tr[u].l==tr[u].r) tr[u].len=0;//没被覆盖的一个线段与下面分开讨论
else//没被覆盖并且不是一个单点就要往上更新了
{
tr[u].len=tr[u*2].len+tr[u*2+1].len;
}
}
void build(int u,int l,int r)//初始化数组
{
tr[u]={l,r,0,0};
if(l==r)
{
return ;
}
//不管其他的更新完成递归
int mid=l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
// pushup(u);
}
void modify(int u,int l,int r,int k)//修改
{
if(tr[u].l>=l&&tr[u].r<=r)//包住
{
tr[u].cnt+=k;//被覆盖
pushup(u);
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u*2,l,r,k);
if(mid<r) modify(u*2+1,l,r,k);
pushup(u);
}
}pushup：当这个cnt>0就说明当前线段树区间在要求的区间之内计算这个区间长度(要加1因为是求一个区间长度，例如到[1,1] 是有一个的1-1+1=1)，else 就是没被当前线段树区间没在矩形区间的情况，那如果是一个叶子节点所包含矩形的长度自然就是0。不是叶子节点就更新自身(根据左右孩子)
build：普通初始化就是不用pushup更新自身
modify：就是寻找被传进来的矩形区间包含的线段树区间更新
最后都更新到线段树tr下标为1的情况下
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
struct line
{
int x;
int y1;//主要维护y轴，记录矩形区间
int y2;
int k;//看这个矩形是否走完了
bool operator<(const struct line& t)
{
return x<t.x;
}
}li[2*10010];//存每个矩形的开始和结束
//这个线段树是按照y轴展开
struct Node
{
int l;
int r;
int cnt;//节点区间被覆盖的次数
int len;//长度，每次都要更新实际上就是
}tr[4*10000];
void pushup(int u)
{
if(tr[u].cnt>0)//被覆盖了，len就是区间长度
tr[u].len=tr[u].r-tr[u].l+1;//+1是因为这是区间不是一个点，1和2这个区间长度为2。2-1+1=2
else if(tr[u].l==tr[u].r) tr[u].len=0;//没被覆盖的一个线段与下面分开讨论
else//没被覆盖并且不是一个单点就要往上更新了
{
tr[u].len=tr[u*2].len+tr[u*2+1].len;
}
}
void build(int u,int l,int r)//初始化数组
{
tr[u]={l,r,0,0};
if(l==r)
{
return ;
}
//不管其他的更新完成递归
int mid=l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
// pushup(u);
}
void modify(int u,int l,int r,int k)//修改
{
if(tr[u].l>=l&&tr[u].r<=r)//包住
{
tr[u].cnt+=k;//被覆盖
pushup(u);
}
else
{
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u*2,l,r,k);
if(mid<r) modify(u*2+1,l,r,k);
pushup(u);
}
}
int main()
{
int x1,x2,y1,y2;
scanf("%d",&n);
int m=0;
for(int i=0;i<n;i++)//扫描线从0开始记录
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
li[m++]={x1,y1,y2,1};//1表示开始
li[m++]={x2,y1,y2,-1};//-1表示结束
}
sort(li,li+m);//依据x排序
build(1,0,10000);
long long res=0;
for(int i=0;i<m;i++)
{
if(i>0)
{
res+=(li[i].x-li[i-1].x)*tr[1].len;//用上次记录的len
}
//y2-1是因为5到2这个区间有四个，我们只要三个(长度是3)
modify(1,li[i].y1,li[i].y2-1,li[i].k);//每次都重新更新线段树
//每次都将总长度重新更新到tr[1]
}
printf("%lld",res);
return 0;
}这篇就到这里啦(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤