首页 > 其他分享 >线段树模版：从入门到入坟

线段树模版：从入门到入坟

时间：2024-08-26 19:47:34浏览次数：9  
标签：qr int 模版 线段 tr mid tag 到入 ql

线段树模版：从入门到入坟

线段树——单点修改

1.求区间最值

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
typedef long long ll;
struct node
{
	int minx;
	int l,r;
}tr[N*4];
int a[N];
void update(int p)
{
	tr[p].minx=min(tr[2*p].minx,tr[2*p+1].minx);
}
void build(int p,int l,int r)
{
	if(l==r){
        tr[p].minx=a[l]; 
		return ;
	}else{
		int mid=(l + r) / 2;
		build(2*p,l,mid);
		build(2*p+1,mid+1,r);
	}
	update(p);
}
// 当前节点为p,[l,r]为当前区间,修改a[pos]->val
void change(int p,int l,int r,int pos,int val)
{
	if(l==r){
		tr[p].minx=val;
		//a[pos]=val;
	}else{
		int mid=(l+r)/2;
		if(pos<=mid) change(2*p,l,mid,pos,val);
		else change(2*p+1,mid+1,r,pos,val);
	}
	//重要！！
	update(p);
}
//[ql,qr]为要查询的区间
int query(int p,int l,int r,int ql,int qr)  //时间复杂度O(logn)
{
	if(ql==l&&qr==r){
		return tr[p].minx;
	}else{
		int mid=(l + r) / 2;
		//[l,mid],[mid+1,r]
		if(qr<=mid) return query(2*p,l,mid,ql,qr);
		else if(ql>mid) return query(2*p+1,mid+1,r,ql,qr);
		else{
			//ql<=mid,qr>mid
			// [ql,mid],[mid+1,qr]
			return minx(query(2*p,l,mid,ql,mid),
				query(2*p+1,mid+1,r,mid+1,qr));
		}
	}
}

2.求区间最值及最值出现次数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
typedef long long ll;
struct info
{
	int minx,mincnt;
};
info operator+(const info &l ,const info &r)
{
	info a;
	a.minx=min(l.minx,r.minx);
	if(l.minx==r.minx)
		a.mincnt=l.mincnt+r.mincnt;
	else if(l.minx<r.minx)
		a.mincnt=l.mincnt;
	else a.mincnt=r.mincnt;
	return a;
}
struct node
{
	info s;
	int l,r;
}tr[N*4];
int a[N];
void update(int p)
{
	tr[p].s=tr[2*p].s+tr[2*p+1].s;
}
void build(int p,int l,int r)
{
	if(l==r){
        tr[p].s={a[l],1}; 
		return ;
	}else{
		int mid=(l + r) / 2;
		build(2*p,l,mid);
		build(2*p+1,mid+1,r);
	}
	update(p);
}
// 当前节点为p,[l,r]为当前区间,修改a[pos]->val
void change(int p,int l,int r,int pos,int val)
{
	if(l==r){
		tr[p].s={val,1};
		//a[pos]=val;
	}else{
		int mid=(l+r)/2;
		if(pos<=mid) change(2*p,l,mid,pos,val);
		else change(2*p+1,mid+1,r,pos,val);
	}
	//重要！！
	update(p);
}
//[ql,qr]为要查询的区间
info query(int p,int l,int r,int ql,int qr)  //时间复杂度O(logn)
{
	if(ql==l&&qr==r){
		return tr[p].s;
	}else{
		int mid=(l + r) / 2;
		//[l,mid],[mid+1,r]
		if(qr<=mid) return query(2*p,l,mid,ql,qr);
		else if(ql>mid) return query(2*p+1,mid+1,r,ql,qr);
		else{
			//ql<=mid,qr>mid
			// [ql,mid],[mid+1,qr]
			return query(2*p,l,mid,ql,mid)+
				query(2*p+1,mid+1,r,mid+1,qr);
		}
	}
    
}

线段树——区间修改

1.求区间和

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int n,m;
struct node
{
    int sum,t;
    int l,r;
}tr[N*4];
int a[N];
void settag(int p,int tag)
{
    tr[p].sum+=tag*(tr[p].r-tr[p].l+1);
    tr[p].t+=tag;
}
void pushdown(int p)
{
    if(tr[p].t)
    {
        tr[2*p].sum+=tr[p].t*(tr[2*p].r-tr[2*p].l+1);
        tr[2*p].t+=tr[p].t;
        tr[2*p+1].sum+=tr[p].t*(tr[2*p+1].r-tr[2*p+1].l+1);
        tr[2*p+1].t+=tr[p].t;
        tr[p].t=0;
    }
}
void update(int p)
{
    tr[p].sum=(tr[2*p].sum+tr[2*p+1].sum);
}
void build(int p,int l,int r)
{
    tr[p].l=l;tr[p].r=r;tr[p].t=0;
    if(l==r){
        tr[p].sum=a[l];
    }else{
        int mid=(l+r)/2;
        build(2*p,l,mid);
        build(2*p+1,mid+1,r);
        update(p);
    }
}
void modify(int p,int l,int r,int ql,int qr,int tag)
{
    if(ql==l&&qr==r)
    {
        settag(p,tag);
        return ;
    }
    pushdown(p);
    int mid=(l+r)/2;
    if(qr<=mid) modify(2*p,l,mid,ql,qr,tag);
    else if(ql>mid)  modify(2*p+1,mid+1,r,ql,qr,tag);
    else{
        modify(2*p,l,mid,ql,mid,tag);
        modify(2*p+1,mid+1,r,mid+1,qr,tag);
    }
    update(p);
 }
int query(int p,int l,int r,int ql,int qr)
{
    if(ql==l&&qr==r)
    {
        return tr[p].sum;
    }
    pushdown(p);
    int mid=(l+r)/2;
    if(qr<=mid) return query(2*p,l,mid,ql,qr);
    else if(ql>mid) return query(2*p+1,mid+1,r,ql,qr);
    else {
        return query(2*p,l,mid,ql,mid)+
        query(2*p+1,mid+1,r,mid+1,qr);
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        char op;
        cin>>op;
        if(op=='Q'){
            int l,r;
            cin>>l>>r;
            int s=query(1,1,n,l,r);
            cout<<s<<endl;
        }else{
            int l,r,d;
            cin>>l>>r>>d;
            modify(1,1,n,l,r,d);
        }
    }
    return 0;
}

2.区间最值

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int n,q;
int a[N];
typedef pair<int,int> PII;
struct node
{
  int minx;
  int t;
}tr[4*N];
void update(int p)
{
  tr[p].minx=min(tr[2*p].minx,tr[p*2+1].minx);
}
void settag(int p,int tag)
{
  tr[p].t=tr[p].t+tag;
  tr[p].minx=tr[p].minx+tag;
}
void pushdown(int p)
{
  if(tr[p].t)
  {
    settag(2*p,tr[p].t);
    settag(2*p+1,tr[p].t);
    tr[p].t=0;
  }
}
void build(int p,int l,int r)
{
  tr[p].t=0;
  if(l==r){
    tr[p].minx=a[l];
    return ;
  }else{
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    update(p);
  }
}
void modify(int p,int l,int r,int ql,int qr,int tag)
{
  if(ql==l&&qr==r){
    settag(p,tag);
    return ;
  }
  int mid=(l+r)/2;
  pushdown(p);
  if(qr<=mid) modify(2*p,l,mid,ql,qr,tag);
  else if(ql>mid) modify(2*p+1,mid+1,r,ql,qr,tag);
  else {
       modify(2*p,l,mid,ql,mid,tag);
       modify(2*p+1,mid+1,r,mid+1,qr,tag);
  }
  update(p);
}
int query(int p,int l,int r,int ql,int qr)
{
  if(ql==l&&qr==r){
    return tr[p].minx;
  }
  int mid=(l+r)/2;
  pushdown(p);
  if(qr<=mid) return query(2*p,l,mid,ql,qr);
  else if(ql>mid) return query(2*p+1,mid+1,r,ql,qr);
  else {
    return min(query(2*p,l,mid,ql,mid),
               query(2*p+1,mid+1,r,mid+1,qr));
  }
  update(p);
}

3.区间乘区间加区间和

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int a[N];
int n,mod;
struct info
{
    int mul;
    int add;
};
struct node
{
    int len,val;
    info t;
}tr[N*4];
info operator+(const info &l,const info &r)
{
    return {l.mul * r.mul % mod,(l.add*r.mul+r.add)%mod};
}
void settag(int p,info tag)
{ 
   tr[p].t=tr[p].t+tag;
   tr[p].val=(tr[p].val*tag.mul+tag.add*tr[p].len)%mod;
}
void pushdown(int p)
{
    info tag=tr[p].t;
    if(tag.mul!=1||tag.add!=0)
    {
       settag(2*p,tag);
       settag(2*p+1,tag);
       tr[p].t={1,0};
    }
}
void update(int p)
{
   tr[p].val=(tr[2*p].val+tr[2*p+1].val)%mod;
}
void build(int p,int l,int r)
{
    tr[p].len=r-l+1;
    tr[p].t={1,0};
    if(l==r){
        tr[p].val=a[l];
        return ;
    }else{
        int mid=(l+r)/2;
        build(2*p,l,mid);
        build(2*p+1,mid+1,r);
        update(p);
    }
}
void modify(int p,int l,int r,int ql,int qr,info tag)
{
    if(ql==l&&qr==r){
        settag(p,tag);
        return ;
    }
    pushdown(p);
    int mid=(l+r)/2;
    if(qr<=mid) modify(2*p,l,mid,ql,qr,tag);
    else if(ql>mid) modify(2*p+1,mid+1,r,ql,qr,tag);
    else
    {
        modify(2*p,l,mid,ql,mid,tag);
        modify(2*p+1,mid+1,r,mid+1,qr,tag);
    }
    update(p);
}
int query(int p,int l,int r,int ql,int qr)
{
    if(ql==l&&qr==r){
        return tr[p].val;
    }
    pushdown(p);
    int mid=(l+r)/2;
    if(qr<=mid) return query(2*p,l,mid,ql,qr);
    else if(ql>mid) return query(2*p+1,mid+1,r,ql,qr);
    else return (query(2*p,l,mid,ql,mid)+query(2*p+1,mid+1,r,mid+1,qr))%mod;
    update(p);
}
signed main()
{
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
     scanf("%lld%lld", &n, &mod);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    int q;
    cin>>q;
    build(1, 1, n);
    for (int i = 0; i < q; i++) {
        int ty;
        cin>>ty;
        if(ty<=2){
         int l, r, d;
         cin>>l>>r>>d;
         if (ty == 2) modify(1, 1, n, l, r, (info){1, d});
         else if (ty == 1) modify(1, 1, n, l, r, (info){d, 0});
        }
        else {
            int l, r;
            cin>>l>>r;
            auto ans = query(1, 1, n, l, r);
            printf("%lld\n", ans);
        }
    }
    return 0;
}

标签：qr,int,模版,线段,tr,mid,tag,到入,ql
From： https://www.cnblogs.com/prioritymygirl/p/18381525

相关文章

  • A2034热门电影视频网站模版源码 仿爱美剧网站模板源码 自适应手机端 内含 视频 资讯
    A2034热门电影视频网站模版源码 仿爱美剧网站模板源码 自适应手机端 内含 视频 资讯 留言热门电影视频网站模版源码-A2034源码介绍A2034是一款仿爱美剧网站模板的热门电影视频网站模版源码。该模版设计精美，功能齐全，支持自适应手机端浏览，为用户提供优质的视频观看体......
  • 模版方法模式
    模板方法模式​ 定义了一个算法的步骤，并允许子类别为一个或多个步骤提供其实践方式。让子类别在不改变算法架构的情况下，重新定义算法中的某些步骤。一、常见使用的场景​ 如Thread类。我们知道在Java中一种使用多线程的方式是定义一个类继承Thread类然后重写其中的run......
  • 牛客周赛 Round 57 D-小红的线段（贪心）
     示例1输入2-1200011011输出112N34Y说明连接第一个点和第二个点，和直线没有交点。连接第三个点和第四个点，和直线有交点。 贪心策略：把点集分为三部分，直线上方m1、直线下方m2以及在直线上m3，我们可以发现：m1中的点和m2中的任意点相连都能通过直线；m3......
  • 区间k小值（可持久化线段树）
    题目描述给定一个序列\(a_1,a_2,\dots,a_n\)，\(m\)次操作，每次给定\(l,r,k\)，问\(a_l,a_{l+1},\dots,a_r\)中第\(k\)小的值。输入第一行一个正整数\(T(1\leqT\leq3)\)，表示测试数据的数量。每组数据第一行\(n,m(1\leqn,m\leq100000)\)。第二行\(n\)个正整数\(a_1,a_2,\dots,a......
  • 线段树（3）——区间操作叠加
    如果我既有区间乘法又有区间加法，我应该怎么办呢？这时候需要写两个标记。假设只写一个标记。标记加法：此时对于乘法操作，因为是将\(t_i+lazy_i\)乘以\(x\)，这样子显然一个懒惰标记做不到。标记乘法：那我加法咋办？那两个标记怎么用呢？首先假设加法标记为\(lazy\)，乘法标记为\(multi......
  • SPFA && dijkstra 模版
    boolSPFA(ints){ intcnt=0; memset(dis,0x3f,sizeof(dis)); queue<int>q; q.push(s); vis[s]=1;dis[v]=0; while(!q.empty()) { intu=q.front();q.pop(); vis[u]=0; for(inti=0;i<g[u].size();i++) { intv=g[u][i].v,w=g[u][i].w; if(d......
  • 线段树维护单调栈——区间查询版本 & 维护递减序列
    这次算是完全搞懂了吧（）（）（#include<bits/stdc++.h>#defineraedread#definecaclcalc#definepbpush_back#definepiipair<int,int>#defineintlonglong#definefifirst#definesesecond#definelsp<<1#definersp<<1|1usingn......
  • 线段树（2）——懒惰标记Lazy Tag（单运算）及例题
    上一篇文章我们讲了线段树的最基本的操作。如果有一种操作叫做区间加法呢？这个时候显然可以依次单点修改，但是时间复杂度太高了。所以可以考虑优化，由于思考过程可能很长，此处直接引入懒惰标记。懒惰标记就是在对一颗树的所有节点进行某种统一操作时，只对根节点做一个标记表示它的子树......
  • 31套科技风PPT模版免费下载
    目录资源名称：31套科技风PPT模板合集资源简介：部分展示：适用人群：资源内容：使用指南：资源下载链接（免费，已设置0个积分下载）资源名称：31套科技风PPT模板合集资源简介：本资源合集提供31套具有现代科技感的PPT模板，专为追求创新和前沿视觉效果的用户设计。这些模板结合了当下流......
  • Prometheus Micrometer jvm告警模版
    基础说明prometheus界面刚开始看起来非常让人疑惑，实际上它的语法非常强大；prometheus既可以读取即使数据（Table），也可以展示趋势图（Graph）；Uselocaltime：选择是否已当前时间展示趋势图查询结构筛选内置命令{筛选条件1，筛选条件2}时间周期内总和(increase(内置命令[5m]))固定......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99