首页 > 其他分享 >线段树

线段树

时间：2025-01-20 20:59:08浏览次数：1  
标签：fr int sum tree mid id 线段 

[线段树]
本质为二叉树
用来区间查询，区间修改，
单点查询，单点修改
运用结构体存储。
struct node{
	int sum,laze;
}tree[N*4];//四倍空间 
//建树
void build_tree(int id,int l,int r){ 
	if(l==r){
		tree[id].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build_tree(id*2,l,mid);
	build_tree(id*2+1,mid+1,r);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
//区间和查询 
int query(int id,int l,int r,int fl,int fr){
	if(l==fl&&r==fr){
		return tree[id].sum;
	}
	int mid=(l+r)/2;
	if(fr<=mid){
		return query(id*2,l,mid,fl,fr);
	}else if(fl>mid){
		return query(id*2+1,mid+1,r,fl,fr);
	}else{
		return query(id*2,l,mid,fl,mid)
			+query(id*2+1,mid+1,r,mid+1,fr);
	}
}
//单点修改 
void change_one(int id,int l,int r,int fn,int cs){
	if(l==r){
		tree[id].sum+=cs;
		return ;
	}
	int mid=(l+r)/2;
	if(fn<=mid)change_one(id*2,l,mid,fn,cs);
	else change_one(id*2+1,mid+1,r,fn,cs);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
//push三件套
void pushup(int id){
	tree[id].sum=tree[id*2].sum+t[id*2+1].sum;
}
void pushdown(int id,int l,int r){
	if(tree[id].laze){
		int mid=(l+r)/2;
		put_tag(id*2,l,mid,tree[id].laze);
		put_tag(id*2+1,mid+1,r,tree[id].laze);
		tree[id].laze=0;
	}
}
void put_tag(int id,int l,int r,int val){
	tree[id].sum+=1ll*(r-l+1)*val;
	tree[id].laze+=val;
}
//区间查询（laze版） 
long long query(int id,int l,int r,int fl,int fr){
	if(fl==l&&fr==r){
		return tree[id].sum;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(fr<=mid){
		return query(id*2,l,mid,fl,fr);
	}else if(fl>mid){
		return query(id*2+1,mid+1,r,fl,fr);
	}else{
		return query(id*2,l,mid,fl,mid)
		+query(id*2+1,mid+1,r,mid+1,fr);
	}
}
//区间加（laze） 
void change(int id,int l,int r,int fl,int fr,long long val){
	if(fl==l&&fr==r){
		put_tag(id,l,r,val);
		return ;
	}
	int mid=(l+r)/2;
	if(fr<=mid){
		change(id*2,l,mid,fl,fr,val);
	}else if(fl>mid){
		change(id*2+1,mid+1,r,fl,fr,val);
	}else{
		change(id*2,l,mid,fl,mid,val);
		change(id*2+1,mid+1,r,mid+1,fr,val);
	}
	pushup(id);
}
1.
accoders线段树 区间最小
思路:
区间查询最小值，把return query(id*2,l,mid,fl,mid)+query(id*2+1,mid+1,r,mid+1,fr);
改为min(query(id*2,l,mid,fl,mid),query(id*2+1,mid+1,r,mid+1,fr));
即可 。
code: 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N];
struct node{
    int sum,laze;
}tree[N*4];
void build(int id,int l,int r){
    if(l==r){
        tree[id].sum=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    tree[id].sum=min(tree[id*2].sum,tree[id*2+1].sum);
}
int query(int id,int l,int r,int fl,int fr){
    if(fl==l&&fr==r){
        return tree[id].sum;
    }
    int mid=(l+r)/2;
    if(fr<=mid){
        return query(id*2,l,mid,fl,fr);
    }else if(fl>mid){
        return query(id*2+1,mid+1,r,fl,fr);
    }else{
        return min(query(id*2,l,mid,fl,mid),query(id*2+1,mid+1,r,mid+1,fr));
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);     
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cout<<query(1,1,n,x,y)<<" ";
    }
    return 0;
}
2.
accoders线段树 带修改的区间最小
思路:
加上单点修改即可，将tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
改为 tree[id].sum=min(tree[id*2].sum,tree[id*2+1].sum);
即可。 
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N];
struct node{
    int sum,laze;
}tree[N*4];
void build(int id,int l,int r){
    if(l==r){
        tree[id].sum=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    tree[id].sum=min(tree[id*2].sum,tree[id*2+1].sum);
}
int query(int id,int l,int r,int fl,int fr){
    if(fl==l&&fr==r){
        return tree[id].sum;
    }
    int mid=(l+r)/2;
    if(fr<=mid){
        return query(id*2,l,mid,fl,fr);
    }else if(fl>mid){
        return query(id*2+1,mid+1,r,fl,fr);
    }else{
        return min(query(id*2,l,mid,fl,mid),query(id*2+1,mid+1,r,mid+1,fr));
    }
}
void change(int id,int l,int r,int fn,int val){
    if(l==r){
        tree[id].sum=val;
        return ;
    }
    int mid=(l+r)/2;
    if(fn<=mid){
        change(id*2,l,mid,fn,val);
    }else{
        change(id*2+1,mid+1,r,fn,val);
    }
    tree[id].sum=min(tree[id*2].sum,tree[id*2+1].sum);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);     
    for(int i=1;i<=m;i++){
        int f;
        cin>>f;
        if(f==1){
            int x,y;
            cin>>x>>y;
            cout<<query(1,1,n,x,y)<<" ";
        }else{
            int x,y;
            cin>>x>>y;
            change(1,1,n,x,y);
        }
    }
    return 0;
}
3.
luogu P3374 【模板】树状数组1
什么，你问为什么树状数组的题要用线段树写？
（别问（划掉））
因为他的区间查询正好是线段树能解决的，也是线段树的弱化版，适合练手。
思路:
考察区间加和区间和，套板子即可。
注:
要开long long。 
code:
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N]; 
struct node{
	long long sum,laze;
}tree[N*4];
void build_tree(int id,int l,int r){
	if(l==r){
		tree[id].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build_tree(id*2,l,mid);
	build_tree(id*2+1,mid+1,r);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
int query(int id,int l,int r,int fl,int fr){
	if(l==fl&&r==fr){
		return tree[id].sum;
	}
	int mid=(l+r)/2;
	if(fr<=mid){
		return query(id*2,l,mid,fl,fr);
	}else if(fl>mid){
		return query(id*2+1,mid+1,r,fl,fr);
	}else{
		return query(id*2,l,mid,fl,mid)
			+query(id*2+1,mid+1,r,mid+1,fr);
	}
}
void change_one(int id,int l,int r,int fn,int cs){
	if(l==r){
		tree[id].sum+=cs;
		return ;
	}
	int mid=(l+r)/2;
	if(fn<=mid)change_one(id*2,l,mid,fn,cs);
	else change_one(id*2+1,mid+1,r,fn,cs);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build_tree(1,1,n);
	for(int i=1;i<=m;i++){
		int f,x,y;
		cin>>f>>x>>y;
		if(f==1){
			change_one(1,1,n,x,y);
		}else{
			cout<<query(1,1,n,x,y)<<"\n";
		}
	}
	return 0;
}
4.
luogu P3368 【模板】树状数组 2
来都来了，直接（水（划掉））做完好了。
思路:
区间加和单点查，要用到laze了。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N];
struct node{
	int sum,laze;
}tree[N*4];
void pushup(int id){
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
void put_tag(int id,int l,int r,int val){
	tree[id].sum+=1ll*(r-l+1)*val;
	tree[id].laze+=val;
}
void pushdown(int id,int l,int r){
	if(tree[id].laze){
		int mid=(l+r)/2;
		put_tag(id*2,l,mid,tree[id].laze);
		put_tag(id*2+1,mid+1,r,tree[id].laze);
		tree[id].laze=0;
	}
}
void build(int id,int l,int r){
	if(l==r){
		tree[id].sum=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
long long query(int id,int l,int r,int fl,int fr){
	if(fl==l&&fr==r){
		return tree[id].sum;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(fr<=mid){
		return query(id*2,l,mid,fl,fr);
	}else if(fl>mid){
		return query(id*2+1,mid+1,r,fl,fr);
	}else{
		return query(id*2,l,mid,fl,mid)
		+query(id*2+1,mid+1,r,mid+1,fr);
	}
}
void change(int id,int l,int r,int fl,int fr,long long val){
	if(fl==l&&fr==r){
		put_tag(id,l,r,val);
		return ;
	}
	int mid=(l+r)/2;
	if(fr<=mid){
		change(id*2,l,mid,fl,fr,val);
	}else if(fl>mid){
		change(id*2+1,mid+1,r,fl,fr,val);
	}else{
		change(id*2,l,mid,fl,mid,val);
		change(id*2+1,mid+1,r,mid+1,fr,val);
	}
	pushup(id);
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int f;
		cin>>f;
		if(f==1){
			int x,y,k;
			cin>>x>>y>>k;
			change(1,1,n,x,y,k);
		}else{
			int x;
			cin>>x;
			cout<<query(1,1,n,x,x)<<"\n";
		}
	}
	return 0;
} 
5.
luogu P3372 【模板】线段树 1
终于是做上线段树的题了。
思路:
区间加和区间查。
code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int a[N];
struct node{
	int sum,laze;
}tree[N*4];
void pushup(int id){
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
void put_tag(int id,int l,int r,int val){
	tree[id].sum+=1ll*(r-l+1)*val;
	tree[id].laze+=val;
}
void pushdown(int id,int l,int r){
	if(tree[id].laze){
		int mid=(l+r)/2;
		put_tag(id*2,l,mid,tree[id].laze);
		put_tag(id*2+1,mid+1,r,tree[id].laze);
		tree[id].laze=0;
	}
}
void build(int id,int l,int r){
	if(l==r){
		tree[id].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
long long query(int id,int l,int r,int fl,int fr){
	if(fl==l&&fr==r){
		return tree[id].sum;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(fr<=mid){
		return query(id*2,l,mid,fl,fr);
	}else if(fl>mid){
		return query(id*2+1,mid+1,r,fl,fr);
	}else{
		return query(id*2,l,mid,fl,mid)
		+query(id*2+1,mid+1,r,mid+1,fr);
	}
}
void change(int id,int l,int r,int fl,int fr,long long val){
	if(fl==l&&fr==r){
		put_tag(id,l,r,val);
		return ;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(fr<=mid){
		change(id*2,l,mid,fl,fr,val);
	}else if(fl>mid){
		change(id*2+1,mid+1,r,fl,fr,val);
	}else{
		change(id*2,l,mid,fl,mid,val);
		change(id*2+1,mid+1,r,mid+1,fr,val);
	}
	pushup(id);
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int f;
		cin>>f;
		if(f==1){
			int x,y,k;
			cin>>x>>y>>k;
			change(1,1,n,x,y,k);
		}else{
			int x,y;
			cin>>x>>y;
			cout<<query(1,1,n,x,y)<<"\n";
		}
	}
	return 0;
}

标签：fr,int,sum,tree,mid,id,线段
From： https://www.cnblogs.com/123lbh321/p/18682513

相关文章

  • 2025 刷题计划 - 线段树
    2025刷题计划-线段树A.P3313[SDOI2014]旅行树剖板子题，开\(C\)棵线段树即可。你可能会说开不下？动态开点不就完了。B.P3924康娜的线段树有意思的一道题，貌似\(O(n\logn)\)解法比\(O(n)\)更难？我实现不出来。首先易得期望的计算方式即为：设当前节点\(x\)的深度为......
  • 使用矩阵乘法维护的线段树
    车人去WC了，找了一个巴蜀毕业的哈工大大三学生来给他代课。那就简单记录一下每天都讲了什么吧CFGYM103470PaimonSegmentTree给定一个长度为\(n\)的序列\(a\)，以及\(m\)次区间加操作和\(q\)次询问（在处理完所有操作后再询问）。询问操作：假设\(a_{i,j}\)表示进行完第......
  • 线段树
    海亮OJ题单维护差分信息P4243[JSOI2009]等差数列若要在序列上处理等差数列，可以考虑差分法。此时，我们不必将差分数组和数列中的元素一一对应（这会影响理解），而是将差分数组中的一个元素和原序列中对应的两个元素关联（我的理解盲区）。这样，使用线段树时，对于（差分数组的下标）区间\([......
  • 【做题记录】2025刷题计划--线段树
    A.「SDOI2014」旅行给每个宗教开一棵线段树，树剖\(+\)线段树单点修改区间查询即可。Code#include<bits/stdc++.h>#definelllonglong#defineilinline#defineread(x){\ charch;\ intfu=1;\ while(!isdigit(ch=getchar()))\ fu-=(ch=='-')<<1;\ x=ch&1......
  • 计算几何~三角形面积、点在三角形内、线段相交代码笔记
    多边形面积的基本公式：鞋带公式。强调多边形点集是按顺序存储；三角形面积基本公式：海伦公式；向量叉积公式；拓扑关系判断：判断点是否在三角形内；判断两条线段是否相交；代码笔记：#pragmaonce#include<iostream>#include<vector>#include<algorithm>#include<cmath>#in......
  • 势能线段树
    简介通过定义势能函数\(\phi(i)\)去描绘整个序列的势能从而推导正确的复杂度。例题P4145上帝造题的七分钟2/花神游历各国典。设\(\phi(i)\)表示第\(i\)个元素的势能。一个元素不停的开根一定会变成\(1\)，不妨将元素\(x\)改写成\(2^k\)的形式。一次开根会将\(......
  • 线段树合并
    简介将多棵线段树的信息统一起来的高效算法称之为线段树合并。通常合并顺序呈树状结构。例题P3224[HNOI2012]永无乡假设所有点都在一个连通块里，那么我们只需要维护一个值域线段树并在上面二分即可。但此时图不连通，我们该如何快速的统计信息呢？对于连边，并查集可以胜任。对......
  • 洛谷题单指南-线段树的进阶用法-P3168 [CQOI2015] 任务查询系统
    原题链接：https://www.luogu.com.cn/problem/P3168题意解读：一个任务管理系统，能够查询在某个时间点运行的任务中优先级最小的k个任务的优先级之和。解题思路：由于总时间n不超过100000，考虑针对所有时刻建立可持久化线段树，根节点为root[i]的线段树维护时刻i的任务情况，节点区间表示......
  • 洛谷题单指南-线段树的进阶用法-P2617 Dynamic Rankings
    原题链接：https://www.luogu.com.cn/problem/P2617题意解读：动态求区间第k小问题。解题思路：树套树的典型应用，具体阐述参考：https://www.cnblogs.com/jcwy/p/18640914100分代码：#include<bits/stdc++.h>usingnamespacestd;constintN=100005;structOp{charop;......
  • 解题报告-论对“线段树思想”的新理解
    解题报告-论对“线段树思想”的新理解一晚上刷了两个线段树知识点，也是见识到了线段树世界的博大精深。我们发现无论怎么写线段树，大体框架都是一样的。那么为什么有那么多种线段树呢？一个是线段树标记的不同。在李超线段树中，每个结点维护的是当前结点最上面那条线的编号，于是更新......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99