烟台五一培训day2笔记
线段树
线段树性质： 修改操作&询问操作？
用来针对区间操作的问题
线段树基础结构：
本质上是一棵二叉树，一定有左右儿子
N=8：1-8的区间，每个节点都有两个区间，就是上面节点区间从中间直接砍掉
只要区间长度没有达到1，就可以继续往左右两边分
线段树有log n层
和分治的分法其实差不多
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],sum[400005],tag[400005],n,m;
int ls(int x){
return x*2;
}
int rs(int x){
return x*2+1;
}
void pushup(int x){
sum[x]=sum[ls(x)]+sum[rs(x)];
}
void add(int x,int l,int r,int k){
sum[x]+=(r-l+1)*k;
tag[x]+=k;
}
void pushdown(int x,int l,int r){
if(tag[x]!=0){
int mid=l+r>>1;
add(ls(x),l,mid,tag[x]);
add(rs(x),mid+1,r,tag[x]);
tag[x]=0;
}
}
void build(int x,int l,int r){
if(l==r){
sum[x]=a[l];
return;
}
int mid=l+r>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
void update(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
return add(x,l,r,k);
}
pushdown(x,l,r);
int mid=l+r>>1;
if(L<=mid)update(ls(x),l,mid,L,R,k);
if(mid<R)update(rs(x),mid+1,r,L,R,k);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return sum[x];
}
pushdown(x,l,r);
int mid=l+r>>1,ans=0;
if(L<=mid)ans+=query(ls(x),l,mid,L,R);
if(mid<R)ans+=query(rs(x),mid+1,r,L,R);
return ans;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int opt;
cin>>opt;
if(opt==1){
int x,y,k;
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}
else{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<'\n';
}
}
}注意理解建树和询问的过程
线段树plus
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],sum[400005],mu[400005],ji[400005],n,q,m;
int ls(int x){
return x<<1;
}
int rs(int x){
return (x<<1)|1;
}
void mul(int x,int l,int r,int k){
(mu[x]*=k)%=m;;
(ji[x]*=k)%=m;
(sum[x]*=k)%=m;
}
void add(int x,int l,int r,int k){
(ji[x]+=k)%=m;
(sum[x]+=k*(r-l+1))%=m;
}
void pushup(int x){
(sum[x]=sum[ls(x)]+sum[rs(x)])%=m;
}
void pushdown(int x,int l,int r){
if(mu[x]!=1){
int m=l+r>>1;
mul(ls(x),l,m,mu[x]);
mul(rs(x),m+1,r,mu[x]);
mu[x]=1;
}
if(ji[x]!=0){
int m=l+r>>1;
add(ls(x),l,m,ji[x]);
add(rs(x),m+1,r,ji[x]);
ji[x]=0;
}
}
void build(int x,int l,int r){
if(l==r){
sum[x]=a[l];
return;
}
int m=l+r>>1;
mu[x]=1;
build(ls(x),l,m);
build(rs(x),m+1,r);
pushup(x);
}
void ch(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
return mul(x,l,r,k);
}
pushdown(x,l,r);
int m=l+r>>1;
if(L<=m)ch(ls(x),l,m,L,R,k);
if(m<R)ch(rs(x),m+1,r,L,R,k);
pushup(x);
}
void jia(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
return add(x,l,r,k);
}
pushdown(x,l,r);
int m=l+r>>1;
if(L<=m)jia(ls(x),l,m,L,R,k);
if(m<R)jia(rs(x),m+1,r,L,R,k);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return sum[x];
}
pushdown(x,l,r);
int m=l+r>>1;
int ans=0;
if(L<=m)(ans+=query(ls(x),l,m,L,R))%=::m;
if(m<R)(ans+=query(rs(x),m+1,r,L,R))%=::m;
return ans;
}
signed main(){
cin>>n>>q>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(q--){
int opt;
cin>>opt;
if(opt==1){
int x,y,k;
cin>>x>>y>>k;
ch(1,1,n,x,y,k);
}
else if(opt==2){
int x,y,k;
cin>>x>>y>>k;
jia(1,1,n,x,y,k);
}
else{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)<<'\n';
}
}
}注意线段树的查询写法和计算顺序，先乘法后加法
扶苏的问题
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1000005;
int sum[4*maxn],tag[4*maxn],tag2[4*maxn],a[maxn],n,m;
int ls(int x){
return x*2;
}
int rs(int x){
return x*2+1;
}
void pushup(int x){
sum[x]=max(sum[ls(x)],sum[rs(x)]);
}
void build(int x,int l,int r){
if(l==r){
sum[x]=a[l];
return;
}
int mid=l+r>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
void add(int x,int l,int r,int k){
tag[x]=k;
tag2[x]=0;
sum[x]=k;
}
void add2(int x,int l,int r,int k){
tag2[x]+=k;
sum[x]+=k;
}
void pushdown(int x,int l,int r){
if(tag[x]!=-1e18){
int mid=l+r>>1;
add(ls(x),l,mid,tag[x]);
add(rs(x),mid+1,r,tag[x]);
tag[x]=-1e18;
}
int mid=l+r>>1;
add2(ls(x),l,mid,tag2[x]);
add2(rs(x),mid+1,r,tag2[x]);
tag2[x]=0;
}
void pt(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
return add(x,l,r,k);
}
pushdown(x,l,r);
int mid=l+r>>1;
if(L<=mid)pt(ls(x),l,mid,L,R,k);
if(R>mid)pt(rs(x),mid+1,r,L,R,k);
pushup(x);
}
void xj(int x,int l,int r,int L,int R,int k){
if(L<=l&&r<=R){
return add2(x,l,r,k);
}
pushdown(x,l,r);
int mid=l+r>>1;
if(L<=mid)xj(ls(x),l,mid,L,R,k);
if(mid<R)xj(rs(x),mid+1,r,L,R,k);
pushup(x);
}
int query(int x,int l,int r,int L,int R){
if(L<=l&&r<=R){
return sum[x];
}
int mid=l+r>>1;
pushdown(x,l,r);
int ans=-1e18;
if(L<=mid)ans=max(query(ls(x),l,mid,L,R),ans);
if(mid<R)ans=max(query(rs(x),mid+1,r,L,R),ans);
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=4*n;i++){
tag[i]=sum[i]=-1e18;
}
build(1,1,n);
while(m--){
int opt;
scanf("%lld",&opt);
if(opt==1){
int x,y,k;
scanf("%lld%lld%lld",&x,&y,&k);
pt(1,1,n,x,y,k);
}
else if(opt==2){
int x,y,k;
scanf("%lld%lld%lld",&x,&y,&k);
xj(1,1,n,x,y,k);
}
else{
int x,y;
scanf("%lld%lld",&x,&y);
cout<<query(1,1,n,x,y)<<'\n';
}
}
}和上面操作类似，注意题意的改法
方差
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
register int x=0;
register bool f=0;
register char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-48;
c=getchar();
}
return f?-x:x;
}
const int maxn=100005;
struct _{
int sum;
bool tag;
}t[maxn<<2];
int a[maxn],n,m;
void pushup(int o){
t[o].sum=t[o<<1].sum+t[o<<1|1].sum;
if(t[o<<1].tag && t[o<<1|1].tag) t[o].tag=1;
else t[o].tag=0;
}
void build(int o,int l,int r){
if(l==r){
t[o].sum=a[l];
if(a[l]==0 || a[l]==1) t[o].tag=1;
else t[o].tag=0;
return ;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
void change(int o,int l,int r,int ql,int qr){
if(l==r){
t[o].sum=sqrt(t[o].sum);
if(t[o].sum==0 || t[o].sum==1) t[o].tag=1;
return;
}
int mid=(l+r)>>1;
if(ql<=mid && !t[o<<1].tag) change(o<<1,l,mid,ql,qr);
if(qr>mid && !t[o<<1|1].tag) change(o<<1|1,mid+1,r,ql,qr);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr){
if(ql<=l && qr>=r) return t[o].sum;
int mid=(l+r)>>1;
int res=0;
if(ql<=mid) res+=query(o<<1,l,mid,ql,qr);
if(qr>mid) res+=query(o<<1|1,mid+1,r,ql,qr);
return res;
}
signed main(){
int _case=0;
while(~scanf("%d",&n)){
printf("Case #%d:\n",++_case);
memset(a,0,sizeof(a));
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
m=read();
while(m--){
int opt=read(),l=read(),r=read();
if(l>r) swap(l,r);
if(opt==0) change(1,1,n,l,r);
else printf("%lld\n",query(1,1,n,l,r));
}
puts("");
}
return 0;
}这道题中要计算的每个数最多被开方7次后就变成1
启发：大于一就暴力修改，0(7 n log n)
等差数列，注意每个节点维护首项和公差
#include<bits/stdc++.h>
using namespace std;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100010;
int n,m,a[maxn];
struct node{
int sum;
int size;
int x,y;
node(){sum=size=x=y=0;}
void init(int v){sum=v;size=1;}
}z[maxn<<2];
node operator+(const node&l,const node&r){
node res;
res.sum=l.sum+r.sum;
res.size=l.size+r.size;
return res;
}
void color(int l,int r,int rt,int x,int y){
z[rt].x+=x;
z[rt].y+=y;
z[rt].sum+=(x+x+(z[rt].size-1)*y)*z[rt].size/2;
}
void push_col(int l,int r,int rt){
if(z[rt].x==0&&z[rt].y==0)return;
int m=(l+r)>>1;
color(lson,z[rt].x,z[rt].y);
color(rson,z[rt].x+z[rt<<1].size*z[rt].y,z[rt].y);
z[rt].x=z[rt].y=0;
}
void build(int l,int r,int rt){
if(l==r){
z[rt].init(a[l]);
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
z[rt]=z[rt<<1]+z[rt<<1|1];
}
node query(int l,int r,int rt,int nowl,int nowr){
if(nowl<=l&&r<=nowr)return z[rt];
push_col(l,r,rt);
int m=(l+r)>>1;
if(nowl<=m){
if(m<nowr)return query(lson,nowl,nowr)+query(rson,nowl,nowr);
else return query(lson,nowl,nowr);
}
else return query(rson,nowl,nowr);
}
void modify(int l,int r,int rt,int nowl,int nowr,int x,int y){
if(nowl<=l&&r<=nowr){
color(l,r,rt,x,y);
return;
}
push_col(l,r,rt);
int m=(l+r)>>1;
if(nowl<=m)modify(lson,nowl,nowr,x,y);
if(m<nowr)modify(rson,nowl,nowr,x,y);
z[rt]=z[rt<<1]+z[rt<<1|1];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
build(root);
cin>>m;
for(int i=1;i<=m;i++){
int opt;
cin>>opt;
if(opt==1){
int l,r;
cin>>l>>r;
cout<<query(root,l,r).sum<<"\n";
}
else{
int l,r,x,y;
cin>>l>>r>>x>>y;
modify(root,l,r,x,y);
}
}
return 0;
}可持久化线段树
#include<bits/stdc++.h>
using namespace std;
int cnt;//总共有多少个节点
struct node
{
int l,r;//左儿子 右儿子编号
int sum;//区间和
node(){
l=r=sum=0;
}
}z[maxn*logn];
void update(int p)
{
z[p].sum = z[z[p].l].sum + z[z[p].r].sum;
}
int build(int l,int r)//当前的区间为l~r 是这段区间对应的节点编号
{
cnt++;
int p=cnt;
if (l==r)
{
z[p].sum = a[l];
return p;
}
int m=(l+r)>>1;
z[p].l = build(l,m);
z[p].r = build(m+1,r);
update(p);
return p;
}
int query(int l,int r,int rt,int nowl,int nowr)
//当前线段树节点编号为rt 对应的区间为l~r 要询问nowl~nowr这段区间的和
{
if (nowl <= l && r <= nowr) return z[rt].sum;
int m=(l+r)>>1;
if (nowl<=m)
{
if (m<nowr) return query(l,m,z[rt].l,nowl,nowr) + query(m+1,r,z[rt].r,nowl,nowr);
else return query(l,m,z[rt].l,nowl,nowr);
}
else return query(m+1,r,z[rt].r,nowl,nowr);
}
int modify(int l,int r,int rt,int p,int v)//返回修改后的新节点编号
//当前线段树节点编号为rt 对应的区间为l~r 要把a[p]+=v
{
cnt++;int q = cnt;//新的节点q用于修改
z[q] = z[rt];
if (l==r)
{
z[q].sum += v;
return q;
}
int m=(l+r)>>1;
if (p<=m)//在左儿子
z[q].l = modify(l,m,z[q].l,p,v);
else
z[q].r = modify(m+1,r,z[q].r,p,v);
update(q);
return q;
}
int main()
{
cin >> n;
for (int i=1;i<=n;i++)
cin >> a[i];
cin >> m;
root[0] = build(1,n);//root[i]代表第i次操作后的根节点是谁
for (int i=1;i<=m;i++)
{
int opt;
cin >> opt;
if (opt==1)
{
int p,v;
cin >> p >> v;
root[i] = modify(1,n,root[i-1],p,v);
}
else
{
int k,l,r;
cin >> k >> l >> r;
cout << query(1,n,root[k],l,r) << "\n";
root[i] = root[i-1];
}
}
return 0;
}注意区间对应的关系
作业
https://www.luogu.com.cn/problem/P4513
https://www.luogu.com.cn/problem/P3372
https://www.luogu.com.cn/problem/P3373
https://www.luogu.com.cn/problem/P1253
https://www.luogu.com.cn/problem/SP1043
https://www.luogu.com.cn/problem/SP1716
https://www.luogu.com.cn/problem/SP2916
https://www.luogu.com.cn/problem/SP2713
http://cdqz.openjudge.cn/ds/1003/
http://cdqz.openjudge.cn/ds/1004/
http://cdqz.openjudge.cn/ds/1005/
https://vjudge.net/problem/HDU-3954#author=GPT_zh
https://hydro.ac/p/bzoj-P3333
https://www.luogu.com.cn/problem/P3919
https://www.luogu.com.cn/problem/P3834
http://cdqz.openjudge.cn/ds/1011/
http://cdqz.openjudge.cn/ds/1001/
http://cdqz.openjudge.cn/ds/1012/
https://vjudge.net/problem/HDU-3333#author=GPT_zh
https://vjudge.net/problem/HDU-4467#author=GPT_zh
https://hydro.ac/p/bzoj-P3251