首页 > 其他分享 >线段树

线段树

时间：2022-10-07 14:56:30浏览次数：74  
标签：标记 int 线段 mid sum 节点

线段树

线段树是一个很优秀的树结构，较简单，功能多，可以维护复杂信息。 可以动态开点，可以打懒标记。

基本概念

线段树是基于分治思想的二叉树。

为了引入线段树，我们来看一个例子：

例 给你一个序列\(a\), 需要支持一下几种操作

​ 1.查询区间\([l, r]\)上的值的和；

​ 2.修改某一个位置上的值；

​ 3.区间\([l, r]\)值\(+k\) ;

其实这是可以用前缀和来做的，但未免慢了些；前两个操作树状数组可以很简洁地完成，但第三个就有些麻烦了，而且效率也是不及线段树的。

类似于树状数组，线段树也是一个节点管理多个原数组的数的一些信息。

线段树的特点：

  1. 每个节点代表一个区间；
  2. 线段树具有唯一的根节点，代表区间是整个统计范围（可持久化除外，有多个）；
  3. 线段树的每个叶子节点都代表一个长度为1的原区间\([x, x]\);
  4. 对于每个节点\([l, r]\) , 其左儿子是\([l, mid]\), 右儿子是\([mid + 1, r]\), 其中 \(mid = (l + r)/2\);

如图：

线段树

普通线段树的实现

线段树的存储

线段树是一种二叉树，所以我们可以采用父子二倍的方法来实现器存储。对于一个节点 \(p\) ,其左儿子是 \(p*2\) ,右儿子是 \(p*2+1\) 。

对于每个节点，都会存储一些信息，所以我们可以用一个结构体来存：

struct node{
    int l, r;//这个节点所维护的区间
    int dat;//这个节点所维护的区间的信息
}tree[4*maxn];

当然，也可以不用结构体，只要在调用相关函数时上传\([l, r]\) 信息即可。

我们可以看到，线段树数组开的空间是\(4*maxn\) ，这是为什么呢。首先我们可以从上图看到，对于整个区间长度是二的n次幂的区间，需要原数组二倍的空间（\(2n-1\)) ,而如果不是二的n次幂呢？那就会多一层，而多的那一层的所占空间是\(2n\) ,而且我们采用的父子二倍的方法，所以就算最后一层没有完全占用，依旧要开上它的空间。

建树

在输入原数组后，就可以先建树了，建完树后进行一些区间的维护也方便。

建树是从根节点开始的，层层向下递归，直到遇到叶子节点后保存叶子节点信息，再向上回溯维护信息。

void build(int p, int l, int r){
    tree[p].l = l, tree[p].r = r;
    if(l == r){				//遇到叶子节点
        tree[p].dat = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(p * 2, l, mid);		//建左子树
    build(p * 2 + 1, mid + 1, r);	//建右子树
    tree[p].dat = tree[p * 2].dat + tree[p * 2 + 1].dat; //维护信息
}


//调用：
build(1, 1, n);

单点修改与区间查询

区间修改

需要用到一个懒惰标记，这样就不用每次修改都把值传下去，而是在后续操作中遇到标记再下传。

模板：P3372 【模板】线段树 1

#include <bits/stdc++.h>
#define maxn 100000
#define int long long
using namespace std;
int m,n;
#define ls k << 1
#define rs k << 1 | 1
#define mid (l + r >> 1)
int tree[maxn << 2], tag[maxn << 2];
void pushup(int k) {
	tree[k] = tree[ls] + tree[rs];
}
void Pushup(int k) {
	tree[k] = tree[ls] + tree[rs];
}
void Build(int k, int l, int r) {
	if (l == r) {
		cin >> tree[k];
		return;
	}
	Build(ls, l, mid);
	Build(rs, mid + 1, r);
	pushup(k);
}
void Add(int k, int l, int r, int v) {
	tag[k] += v;
	tree[k] += 1ll * (r - l + 1) * v;
}
void pushdown(int k, int l, int r) {
	if (!tag[k]) return;
	Add(ls, l, mid, tag[k]);
	Add(rs, mid + 1, r, tag[k]);
	tag[k] = 0;
}
void Modify(int k, int l, int r, int x, int y, int v) {
	if (l >= x && r <= y) return Add(k, l, r, v);
	pushdown(k, l, r);
	if (x <= mid) Modify(ls, l, mid, x, y, v);
	if (mid < y) Modify(rs, mid + 1, r, x, y, v);
	pushup(k);
}
int Query(int k, int l, int r, int x, int y) {
	if (l >= x && r <= y) return tree[k];
	pushdown(k, l, r);
	int ret = 0;
	if (x <= mid) ret += Query(ls, l, mid, x, y);
	if (mid < y) ret += Query(rs, mid + 1, r, x, y);
	return ret;
}
signed main() {
	cin >> n >> m;
	Build(1, 1, n);
	for (int i = 1, opt, x, y, z; i <= m; i++) {
		cin >> opt >> x >> y;
		if (opt == 1) {
			cin >> z;
			Modify(1, 1, n, x, y, z);
		}
		if(opt == 2){
			cout<<Query(1, 1, n, x, y)<<endl;
		}
	}
	return 0;
}

区间乘法：需要维护两个懒惰标记，一个加一个乘，在下传时要注意顺序。

模板：P3373 【模板】线段树 2

#include<bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int n, m, mod;
int a[maxn];
struct node{
	int l, r, tag1, tag2, sum;
}t[4*maxn];
void build(int p, int l, int r){
	t[p].l = l, t[p].r = r, t[p].tag2 = 1;
	if(l == r){
		t[p].sum = a[l]%mod;
		return;
	}
	int mid = l + r >> 1;
	build(p*2, l, mid);
	build(p*2+1, mid + 1, r);
	t[p].sum = (t[p*2].sum + t[p*2+1].sum) %mod;
}
void spread(int p){
	t[p*2].sum = (t[p].tag2 * t[p*2].sum + (t[p*2].r - t[p*2].l + 1) * t[p].tag1)%mod ;
    t[p*2+1].sum = (t[p].tag2 * t[p*2+1].sum + (t[p].tag1 * (t[p*2+1].r - t[p*2+1].l + 1)) )%mod ;
    t[p*2].tag2 = (t[p*2].tag2 * t[p].tag2)%mod ;
    t[p*2+1].tag2 = (t[p*2+1].tag2 * t[p].tag2)%mod ;
	t[p*2].tag1 = (t[p*2].tag1 * t[p].tag2 + t[p].tag1)%mod ;
    t[p*2+1].tag1 = (t[p*2+1].tag1 * t[p].tag2 + t[p].tag1) %mod;
    t[p].tag2 = 1;
	t[p].tag1 = 0;
}
void add(int p, int x, int y, int k){
	if(x <= t[p].l && y >= t[p].r){
		t[p].sum = (t[p].sum + k * (t[p].r - t[p].l + 1)) % mod;
		t[p].tag1 = (t[p].tag1 + k)%mod ;
		return;
	}
	spread(p);
	t[p].sum = (t[p*2].sum + t[p*2+1].sum) ;
	int mid = t[p].l + t[p].r >> 1;
	if(x <= mid) add(p*2, x, y, k);
	if(y > mid) add(p*2+1, x, y, k);
	t[p].sum = (t[p*2].sum + t[p*2+1].sum) ;
}
void mul(int p,int x,int y,int k){
	if(t[p].l>=x && t[p].r<=y){
		t[p].tag1 = (t[p].tag1 * k) ;
		t[p].tag2 = (t[p].tag2 * k) ;
		t[p].sum = (t[p].sum * k) ;
		return ;
	}
	spread(p);
    t[p].sum = t[p*2].sum + t[p*2+1].sum;
	int mid = (t[p].l + t[p].r) >> 1;
	if(x <= mid) mul(p*2, x, y, k);
	if(mid < y) mul(p*2+1, x, y, k);
	t[p].sum = (t[p*2].sum + t[p*2+1].sum)%mod;
}
int ask(int p, int x, int y){
	if(t[p].l >= x && t[p].r <= y){
		return t[p].sum;
	}
	spread(p);
	int as=0;
	int mid = (t[p].l+t[p].r)>>1;
	if(x <= mid) as = (as + ask(p*2, x, y))%mod ;
	if(mid < y) as = (as + ask(p*2+1, x, y))%mod ;
	return as;
}
signed main(){
	cin >> n >> m >> mod;
	for(int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	for(int i = 1, opt, x, y, k; i <= m; i++){
		cin >> opt;
		if(opt == 1){
			cin >> x >> y >> k;
			mul(1, x, y, k);
		}
		if(opt == 2){
			cin >> x >> y >> k;
			add(1, x, y, k);
		}
		if(opt == 3){
			cin >> x >>y;
			cout << ask(1, x, y)%mod << endl;
		}
	}
	return 0;
}

线段树应用

扫描线

权值线段树

所谓权值线段树就是在值域上建一棵线段树，当插入一个数时，其位置加一。

例题： [USACO08FEB]Hotel G

优化：动态开点

我们可以看到，在值域上开一棵线段树是非常危险的，这很可能会爆空间

可持久化线段树

可持久化线段树即为可保存历史版本的线段树。

在一个历史版本上修改时，只用新建被修改了的节点，没有修改的节点直接指向原来的历史版本就行。

根节点仍然是调用这棵树的入口，会有很多根节点，每一个根节点都是其所在的历史版本的入口。

可持久化数组

模板：P3919 【模板】可持久化线段树 1（可持久化数组）

#include <bits/stdc++.h>
#define maxn 1000012
using namespace std;
struct node{
	int lc, rc, dat;
}t[30*maxn];
int root[maxn], tot;
int n, m, a[maxn], cnt;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int build(int l, int r){
	int p = ++tot;
	if(l == r){
		t[p].dat = a[l];
		return p;
	}
	int mid = (l + r) >> 1;
	t[p].lc = build(l, mid);
	t[p].rc = build(mid + 1, r);
	t[p].dat = max(t[t[p].lc].dat , t[t[p].rc].dat);
	return p;
}
int change(int now, int l, int r, int x, int val){
	int p = ++tot;
	t[p] = t[now];
	if(l == r){
		t[p].dat = val;
		return p;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) t[p].lc = change(t[now].lc, l, mid, x, val);
	else t[p].rc = change(t[now].rc, mid+1, r, x, val);
	t[p].dat = max(t[t[p].lc].dat , t[t[p].rc].dat);
	return p;
}
int query(int p, int l, int r, int x){
	if (l == r) return t[p].dat;
	int mid = (l + r) >> 1;
	if (x <= mid) return query(t[p].lc, l, mid, x);
	else return query(t[p].rc, mid + 1, r, x);
}
signed main(){
	n = read(), m = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	root[0] = build(1, n);
	for(int i = 1, now, opt, x, val; i <= m; i++){
		now = read(), opt = read();
		if(opt == 1){
			x = read(), val = read();
			root[i] = change(root[now], 1, n, x, val);
		}
		if(opt == 2){
			x = read();
			cout << query(root[now], 1, n, x) <<endl;
			root[i] = root[now];
		}
	}
}

Tips

1.标记永久化

标记永久化就少了每次都上传下传，常数会小很多。

标记永久化的原理简单来说就是修改时一路更改被影响到的点，询问时则一路累加路上的标记，从而省去下传标记的操作。

//以下抄自标记永久化 - wozaixuexi - 博客园 (cnblogs.com)

3.0 说明

这里以区间修改区间求和的线段树为例。

线段树中编号为p的结点的值和标记分别为val[p]和mark[p]。

3.1 建树

标记永久化线段树的建树和标记不永久化线段树的建树没有什么区别，这里就不在赘述，直接上代码吧。

void Build(int p,int l,int r)
{
    if(l==r) {scanf("%lld",&val[p]);return;}
    int mid=(l+r)>>1;
    Build(p<<1,l,mid);//递归建左子树
    Build(p<<1|1,mid+1,r);//递归建右子树
    val[p]=val[p<<1]+val[p<<1|1];//这里是要向上更新一下的
}

3.2 区间修改

0.设要将区间[xy]中的数都加上v。

1.一路走下去同时更新路上受此次修改影响的节点的值，即val[p]+=(y-x+1)*v。

2.当目前结点所代表的区间与待修改区间完全重合时，更新标记，返回，即mark[p]+=v;

void add(int p,int l,int r,int x,int y,long long v)
{
    val[p]+=(y-x+1)*v;//更新该结点的权值 
    if(l==x&&r==y) {mark[p]+=v;return;}//更新标记 
    int mid=(l+r)>>1;
    if(y<=mid) add(p<<1,l,mid,x,y,v);
    else if(x>mid) add(p<<1|1,mid+1,r,x,y,v);
    else add(p<<1,l,mid,x,mid,v),add(p<<1|1,mid+1,r,mid+1,y,v);
}

有人可能会问：标记更新后直接返回的话下面的结点不就没更新了吗？

慢慢来嘛，往下看就明白啦。

3.3 区间询问

0.设要要区间[x,y]中的数的总和。

1.一路走下去同时累加路上的标记，因为在修改操作中标记并没有下传，所以要这样子，即ad+=mark[p]。

2.当目前结点所代表的区间与待修改区间完全重合时，返回当前结点的值与累加下来的标记乘上询问区间长度的和，即return val[p]+(y-x+1)*ad。

int ask(int p,int l,int r,int x,int y,int ad)//ad为一路上累加的标记 
{
    if(l==x&&r==y) return val[p]+(y-x+1)*ad;
    int mid=(l+r)>>1;
    if(y<=mid) return ask(p<<1,l,mid,x,y,ad+mark[p]);
    if(x>mid) return ask(p<<1|1,mid+1,r,x,y,ad+mark[p]);
    return ask(p<<1,l,mid,x,mid,ad+mark[p])+ask(p<<1|1,mid+1,r,mid+1,y,ad+mark[p]);
}

2.非递归进行线段树的操作 —— ZKW 线段树。

标签：标记,int,线段,mid,sum,节点
From： https://www.cnblogs.com/Echo-djc/p/16759717.html

相关文章

  • 2022.10.3线段树复习笔记（未完待续）
    线段树原理及存储：如图，1即为根节点，存储着[1,5]的整个区间和，‘1’为左边界，‘5’为右边界，所以此节点表示的是[1,5]这个区间。线段树的每个节点向下二分，左儿子的编号为此节......
  • 线段树精选题
    SP2713GSS4-CanyouanswerthesequeriesIV题目大意\(n\)个数，和在\(10^18\)范围内，两种操作:区间开方下取整，查询区间和。思路区间开方，其实也是区间修改，只是每个元......
  • P3834 【模板】可持久化线段树 2
    P3834主席树模板，求区间第k小。1#include<bits/stdc++.h>2usingnamespacestd;3#definelctr[i].ch[0]4#definerctr[i].ch[1]5#defineLctr[j].ch[0......
  • 动态开点线段树
    引入在普通的线段树中，我们一般要开\(4N\)的数组以避免越界。然而，在一些题目中，空间限制并不允许我们这样做。考虑如下问题：有一个长度为\(n\)的数组，初始全部为\(0\)......
  • 李超线段树 学习笔记
    Idea主要用于动态维护一个线段或直线集合，支持在平面直角坐标系中插入一条线段或者直线，以及查询某一横坐标上的最值。考虑在x轴上建立一棵线段树，每一个节点\([l,r]\)......
  • 探求|线段或棱上是否存在一个点
    ......
  • [模板]zkw线段树
    讲解在这里[还有一个](https://wenku.baidu.com/view/f27db60ee87101f69e319544.html)A.数列操作单点修改，区间查询code//正青春的年华，就是应该献给直指星辰的梦想啊！......
  • 「CF1455G」Forbidden Value 题解 (DP，线段树合并)
    题目简介已知初始值\(x=0\)，给定下面\(2\)种命令：set\(y\)\(v\)，令\(x=y\)，或花费\(v\)元钱删除该命令；if\(y\)...end，如果\(x==y\)，执行if...end中的命令，否则跳......
  • 李超线段树
    李超发明的一种维护平面上有限值域的直线或线段纵坐标大小的一种数据结构。因为是根据线段树研发的，代码也基于线段树，所以叫李超线段树。常规支持：插入一条线段或直线。......
  • 吉司机线段树
    luoguP6242线段树3蒟蒻的代码//线段树3//需要支持的操作：//修改：区间加，区间取min，区间求和//查询：区间最大值，区间历史最大值//瓶颈在于区间取min//引入区间最大......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99