树状数组:
一共需要三个函数:
①lowbit(int x)
②add(int x,int p)
③query(int x)
1.动态求连续区间和
给定n个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列[a,b]的连续和。
输入格式
第一行包含两个整数n和m,分别表示数的个数和操作次数。
第二行包含n个整数,表示完整数列。
接下来m行,每行包含三个整数k,a,b(k=0,表示求子数列[a,b]的和;k=1,表示第a个数加b)。
数列从1开始计数。
输出格式
输出若干行数字,表示k=0时,对应的子数列[a,b]的连续和。
数据范围
1≤n≤100000
1≤m≤100000
1≤a≤b≤n
输入样例:
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
代码:
#include<iostream>#include<algorithm> using namespacestd; const int N=100010; intn,m; inta[N],tr[N]; int lowbit(intx) { return x&-x; } void add(int x,intp) { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=p; } int query(intx) { int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tr[i]; returnans; } intmain() { inti,j,x,y,k; cin>>n>>m; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) add(i,a[i]); for(i=1;i<=m;i++) { cin>>k>>x>>y; if(k==1) { add(x,y); } else{ cout<<query(y)-query(x-1)<<endl; } } return 0; }
2.数星星
天空中有一些星星,这些星星都在不同的位置,每个星星有个坐标。
如果一个星星的左下方(包含正左和正下)有kk颗星星,就说这颗星星是kk级的。
例如,上图中星星5是3级的(1,2,4在它左下),星星2,4是1级的。
例图中有1个0级,2个1级,1个2级,1个3级的星星。
给定星星的位置,输出各级星星的数目。
换句话说,给定N个点,定义每个点的等级是在该点左下方(含正左、正下)的点的数目,试统计每个等级有多少个点。
输入格式
第一行一个整数N,表示星星的数目;
接下来N行给出每颗星星的坐标,坐标用两个整数x,y表示;
不会有星星重叠。星星按y坐标增序给出,y坐标相同的按x坐标增序给出。
输出格式
N行,每行一个整数,分别是0级,1级,2级,……,N−1级的星星的数目。
数据范围
1≤N≤15000,
0≤x,y≤32000
输入样例:
5
1 1
5 1
7 1
3 3
5 5
输出样例:
1
2
1
1
0
解题思路:这道题只需要根据x坐标来建立树状数组,求由于树状数组下标从1开始,故在读入时x坐标要加1,先统计在该星星前有多少个星星,在进行add操作,加上这颗星星
类似于求小于x的横坐标个数的前缀和。
代码:
#include<iostream>#include<cstdio> using namespacestd; const int N=32010; inttr[N],level[N]; int lowbit(intx) { return x&-x; } void add(int x,intt) { for(int i=x;i<N;i+=lowbit(i)) tr[i]+=t; } int query(intx) { int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tr[i]; returnans; } intmain() { inti,j,n,x,y; cin>>n; for(i=0;i<n;i++) { scanf("%d%d",&x,&y); x++; level[query(x)]++; add(x,1); } for(i=0;i<n;i++) printf("%d ",level[i]); return 0; }
线段树操作
①pushup:用字节点信息更新当前节点信息
②build:在一段区间上初始化线段树
③modify:修改
④query:查询
线段树模拟:
1.动态求连续区间和
线段树做法:
#include<iostream> using namespacestd; const int N=100010; intn,m; intw[N]; structnode { intl,r; intsum; }tr[N*4]; void pushup(intu) { tr[u].sum=tr[u*2].sum+tr[u*2+1].sum; } void build(int u,int l,intr) { 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); } } int query(int u,int l,intr) { if(tr[u].l>=l&&tr[u].r<=r) returntr[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); returnsum; } void modify(int u,int x,intv) { if(tr[u].l==tr[u].r) tr[u].sum+=v; else{ int mid=tr[u].l+tr[u].r>>1; if(x<=mid) modify(u<<1,x,v); elsemodify(u<<1|1,x,v); pushup(u); } } intmain() { inti,j,k,x,y; cin>>n>>m; for(i=1;i<=n;i++) cin>>w[i]; build(1,1,n); while(m--) { cin>>k>>x>>y; if(k==0) cout<<query(1,x,y)<<endl; elsemodify(1,x,y); } return 0; }
2.数列区间最大值
输入一串数字,给你M个询问,每次询问就给你两个数字X,Y,要求你说出X到Y这段区间内的最大数。
输入格式
第一行两个整数N,M表示数字的个数和要询问的次数;
接下来一行为N个数;
接下来M行,每行都有两个整数X,Y。
输出格式
输出共M行,每行输出一个数。
数据范围
1≤N≤105,
1≤M≤106
1≤X≤Y≤N
数列中的数字均不超过231−1
输入样例:
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例:
5
8
解题思路:根据线段树来处理,此时结构体里应该添加的一个数是maxn,来记录当前的最大值,在建树时更新当前树根的最大值,
在算区间最大值时,先判断左右是否在区间内,若不在判断该点的mid与左右区间是否有交集,然后取最大的。
代码:
#include<iostream>#include<cstdio>#include<bits/stdc++.h> using namespacestd; const int N=100010; intw[N]; structnode { intl,r; intmaxn; }tr[N*4]; void build(int u,int l,intr) { if(l==r) tr[u]={l,r,w[r]}; else{ tr[u]={l,r}; int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); tr[u].maxn=max(tr[u*2].maxn,tr[u*2+1].maxn); } } int query(int u,int l,intr) { if(tr[u].l>=l&&tr[u].r<=r) returntr[u].maxn; int mid=tr[u].l+tr[u].r>>1; int ans=INT_MIN; if(l<=mid) ans=query(u<<1,l,r); if(r>mid) ans=max(ans,query(u<<1|1,l,r)); returnans; } intmain() { intn,m,i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&w[i]); build(1,1,n); intl,r; while(m--) { scanf("%d%d",&l,&r); printf("%d ",query(1,l,r)); } return 0; }