首页 > 其他分享 >【数据结构】- 线段树

【数据结构】- 线段树

时间:2024-07-19 09:08:07浏览次数:15  
标签:node int 线段 tree 区间 数据结构 节点

前言

线段树用于维护区间上的值,可以在 $O(\log n)$ 的时间复杂度内实现单点,区间修改及查询。并且所有满足结合律的运算都可以用线段树进行加速。

基本操作

建树

给你长度为 $n$ 的正整数序列 $A$,要你实现单点修改与区间查询。(加和)

这就是线段树的基本题目。线段树,字面上来看就是把线段映射到树上,可以想到每个节点代表一个区间。

那么我们可以把每个区间分成两半,作为节点的左右子节点。

最常见的树左右子节点就是 $rt \times 2$ 和 $rt \times 2 + 1$(堆式存储)。可以直接开 $4$ 倍空间。

可以知道,如果有 $n$ 个叶子节点,最大值是 $2 ^ {\lfloor \log n \rfloor + 1}$ 的。当 $n = 2^x + 1$ 时,$\dfrac{2 ^ {\lfloor \log n \rfloor + 1}}{n}$ 取得最大值 $4n - 5$。

如图就是 $n = 5, A = {1, 2, 3, 4, 5}$ 时的线段树(加和)。

我们可以发现,对于每个区间 $[x,y]$,都被分成了 $[x, \lfloor \dfrac{x + y}{2} \rfloor]$ 和 $[\lfloor \dfrac{x + y}{2} \rfloor + 1, y]$ 这两个区间。如果我们令根节点的深度为 $0$,那么可以发现整棵树的深度不超过 $\log n + 1$,这也就意味着我们至多经过 $\log n$ 条边就可以找到一个区间。

建树时我们可以递归建树,如果 $l = r$,也就意味着到了单点,这时直接赋值。返回时再更新节点值即可。

void pushup (int node) { tree[node] = tree[node << 1] + tree[(node << 1) + 1]; }

void build (int node, int l, int r){
	if (l == r){
		tree[node] = ta[l];
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	build ((node << 1), l, mid);
	build ((node << 1) + 1, mid + 1, r);
  	pushup (node);
}

因为深度不超过 $\log n +1$,所以复杂度应该是 $O(\log n)$ 的。

单点修改

当我们单点修改时,只需要想建树那样遍历,如果遍历到单点就直接修改,然后返回,更新。

void modify (int node, int l, int r, int a, int c){
	if (l == r){
		tree[node] = c;
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	if (a <= mid) modify ((node << 1), l, mid, a, b);
	else modify ((node << 1) + 1, mid + 1, r, a, b);
  	pushup (node);
}

区间查询

单点查询很好做,关键就是区间查询。

对于查询区间,我们一定可以把它分成几个序列上的区间,对应树上的节点。关键就是这些节点。

设当前遍历到的区间为 $[l,r]$,要查询的区间为 $[s,t]$。

如果要查询的区间在左边,可以发现一定是 $s \le \lfloor \dfrac{x + y}{2} \rfloor$;如果在右边,那么一定是 $t \gt \lfloor \dfrac{x + y}{2} \rfloor$。没有等于的情况是因为向下取整,如果等于就已经被左边的区间包含了,不能算重,所以没有等于。

那么把左右区间累加起来,就是这个区间的贡献,直接返回即可。

long long query (int node, int l, int r, int s, int t) {
	if (s <= l && r <= t) return tree[node];
	
	int mid = l + ((r - l) >> 1);
	long long ret = 0;
	if (s <= mid) ret += query (node << 1, l, mid, s, t);
	if (t > mid) ret += query ((node << 1) + 1, mid + 1, r, s, t);
	return ret;
}

至此,基本的,没有任何其他东西的一个纯粹的线段树我们就打完了。可以发现每个操作都是基于线段树的层数来定的复杂度,所以都是 $O(\log n)$ 的。

但是拓展操作远远不止于此,上题!

区间修改

P3372 【模板】线段树 1

你长度为 $n$ 的正整数序列 $A$,要你实现区间修改与区间查询。

这题唯一的不同就在于区间修改。如果每个暴力单点修改的话,复杂度 $O(n \log n)$,会爆炸。

这时就要引入一种叫懒惰标记的东西。

还是遍历,当这个区间在查询区间中,我们就先修改它的值,给它挂上懒惰标记,但不修改它子节点的值。

你可能已经想到了,再一次遍历的时候就可以下传懒惰标记,以达到区间修改的目的。

void pushdown (int node, int l, int r) {
	int ls = node << 1, rs = (node << 1) + 1, mid = l + ((r - l) >> 1);
	if (lazy[node]) {
		int x = lazy[node];
		tree[ls] += (mid - l + 1) * x; tree[rs] += (r - mid) * x;
		lazy[ls] += x; lazy[rs] += x;
		lazy[node] = 0;
	}
}

void modify (int node, int l, int r, int s, int t, long long c) {
	if (s <= l && r <= t) {
		tree[node] += (r - l + 1) * c;
		lazy[node] += c;
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	pushdown (node, l, r);
	if (s <= mid) modify (node << 1, l, mid, s, t, c);
	if (t > mid) modify ((node << 1) + 1, mid + 1, r, s, t, c);
	pushup (node);
}

动态开点线段树

线段树的时间复杂度虽然小,但是空间复杂度大,有 $4n$,如何来优化呢?

我们可以把懒惰标记的思想用在节点上面,就成了动态开点。也就是访问到这个节点时再创建这个节点,但不能用 $rt \times 2$ 这种来存储了,必须另外专门存储。

就拿单点修改来举例吧。

int n, tot, rt;
int tree[N << 1], ls[N << 1], rs[N << 1];

void modify (int &node, int l, int r, int s, int c) {
	if (!node) node = ++tot;
	if (l == r) {
		tree[node] = c;
		return ;
	}
  
	int mid = l + ((r - l) >> 1);
	if (s <= mid) modify (ls[node], l, mid, s, c);
	else modify (rs[node], mid + 1, r, s, c);
	pushup (node);
}

小清新线段树

上题。

P4145 上帝造题的七分钟 2 / 花神游历各国

给你一个长度为 $n$ 的正整数序列 $A$,要实现区间开方与区间求和

注意到,区间开方是从未有过的操作,只能一个一个单点修改,复杂度肯定爆炸。

但是 $\sqrt 1 = 1,\sqrt 0 = 0$,我们可以另存一个最大值。如果这个区间的最大值小于等于 $1$ 的话,就不用修改了。

数列里的数不超过 $10^{12}$。

$$\sqrt{10^{12}} = 10^6 \to \sqrt{10^6} = 1000 \to \sqrt{1000} \approx 31.62 \to \sqrt{31.62} \approx 5.62 \to \sqrt{5.62} \approx 2.37 \to \sqrt{2.37} \approx \approx 1.53$$

也就是说至多 $6$ 次就可以让数列里面的数成为 $1$,所以这个优化效果拔群。

void modify (int node, int l, int r, int s, int t) {
	if (l == r) {
		tree[node] = sqrt (tree[node]);
		mx[node] = sqrt (mx[node]);
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	if (s <= mid && mx[node << 1] > 1) modify (node << 1, l, mid, s, t);
	if (t > mid && mx[(node << 1) + 1] > 1) modify ((node << 1) + 1, mid + 1, r, s, t);
	pushup (node);
}

权值线段树

我们都知道,线段树用来维护的是序列上的元素。那如果维护序列上的元素个数呢?这就是权值线段树。

P1908 逆序对

给你一个长度为 $n$ 的正整数序列 $A$,需要你找出 $A$ 中所有满足 $i \lt j$ 且 $A_i \gt A_j$ 的 $(i,j)$ 二元组个数。

这道题维护的就是元素个数,而不是元素值。

用权值线段树解题的话,我们需要离散化,然后把每个下标看做元素值,元素值则看做下标对应元素个数。

就像这样,然后我们就可以在上面做操作了。

void modify (int node, int l, int r, int c) {
	if (l == r) {
		tree[node]++;
		return ;
	}
	
	int mid = l + ((r - l) >> 1);
	if (c <= mid) modify (node << 1, l, mid, c);
	else modify ((node << 1) + 1, mid + 1, r, c);
	pushup (node);
}

int query (int node, int l, int r, int s, int t) {
	if (s <= l && r <= t) return tree[node];
	
	int mid = l + ((r - l) >> 1), ret = 0;
	if (s <= mid) ret += query (node << 1, l, mid, s, t);
	if (t > mid) ret += query ((node << 1) + 1, mid + 1, r, s, t);
	pushup (node);
	return ret;
}

int main () {
	
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf ("%lld", &a[i]);
		A[i] = a[i];
	}
	sort (A + 1, A + n + 1);
	int ret = unique (A + 1, A + n + 1) - A - 1;
	for (int i = 1; i <= n; ++i) a[i] = lower_bound (A + 1, A + ret + 1, a[i]) - A;
	
	printf ("%lld", ans);
	
	return 0;
}

可持久化线段树

可持久化也分为部分可持久化与完全可持久化。

一般可持久化的题目都会让你记录一个历史版本,这个历史版本就是每一个操作所产生的新的线段树。

也就是说,如果我在原本的线段树上做了一个单点修改操作,那么就会多一个历史版本是操作后的线段树,版本与操作对应。

部分可持久化就是可以访问所有历史版本,但是只有最新版本可以修改。

完全可持久化就是可以访问,修改所有历史版本。

如果我们对每一个操作都开一个线段树呢?

ver. 0 就是未做修改的线段树,ver. 1 是单点修改。

都知道,这样肯定会爆空间,但是我把它们与原线段树比较,发现修改经过的节点是条链。

那么我们为什么不考虑把这条链加到原线段树上面呢?

这时候,主席树(可持久化权值线段树)便应运而生了。

可以发现,新增的节点不仅构成了链,还连接了对应的节点。并且节点数是不超过 $\log n$ 的。

但是主席树必须要用动态开点线段树,不然空间就会像前面一样爆掉。

我们可以对每一颗新增出来的链开一个数组来记录它的根节点,方便遍历,操作基本跟线段树是一样的。


P3834 【模板】可持久化线段树 2

静态区间第 $k$ 小。

我们可以把这个问题拆成区间 $[1,r]$ 的静态第 $k$ 小,就可以用主席树来维护。那么如果我们要求区间 $[l,r]$,只需要用一下前缀和的思想,用 $[1,r] - [1,l-1]$ 就可以了。

注意离散化。

struct Seg {
	int ls, rs;
	int sum;
} tree[N * 20];

int build (int l, int r) {
	int node = ++tot;
	if (l == r) return node;
	
	int mid = l + ((r - l) >> 1);
	tree[node].ls = build (l, mid);
	tree[node].rs = build (mid + 1, r);
	return node;
}

int modify (int v, int l, int r, int s) {
	int node = ++tot;
	tree[node] = tree[v];
	tree[node].sum++;
	
	if (l == r) return node;
	
	int mid = l + ((r - l) >> 1);
	if (s <= mid) tree[node].ls = modify (tree[node].ls, l, mid, s);
	else tree[node].rs = modify (tree[node].rs, mid + 1, r, s);
	return node;
}

int query (int l, int r, int s, int t, int k) {
	if (l == r) return l;
	
	int mid = l + ((r - l) >> 1), x = tree[tree[t].ls].sum - tree[tree[s].ls].sum;
	if (k <= x) return query (l, mid, tree[s].ls, tree[t].ls, k);
	else return query (mid + 1, r, tree[s].rs, tree[t].rs, k - x);
}

int main () {
	
	ios::sync_with_stdio (false);
	cin.tie (0); cout.tie (0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		b[i] = a[i];
	}
	
	sort (b + 1, b + n + 1);
	len = unique (b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; ++i) a[i] = lower_bound (b + 1, b + len + 1, a[i]) - b;
	
	
	rt[0] = build (1, len);
	for (int i = 1; i <= n; ++i) rt[i] = modify (rt[i - 1], 1, len, a[i]);
	
	while (m--) {
		int l, r, k;
		cin >> l >> r >> k;
		cout << b[query (1, len, rt[l - 1], rt[r], k)] << endl;
	}
	
	return 0;
}

标签:node,int,线段,tree,区间,数据结构,节点
From: https://www.cnblogs.com/Xeanin/p/18310752

相关文章

  • 基于Python语言的入门算法和数据结构(持续更新中,求关注一波)[链表 栈 队列 复杂度 操作]
    这篇文章主要是讲的Python语言的算法,本人还在不断记笔记中,文章也会持续更新,内容比较浅薄,请大家指教另外推荐一个比较好用的记笔记的软件Typora,自己已经使用很久了,感觉不错。。。虽然但是还是有欠缺。目录第一章算法概述1.1什么是数据结构?01数据结构都有哪些组成方式02......
  • Java中的并发数据结构与多线程优化技术
    Java中的并发数据结构与多线程优化技术大家好,我是微赚淘客系统3.0的小编,是个冬天不穿秋裤,天冷也要风度的程序猿!在多线程编程中,并发数据结构和优化技术是提高系统性能和可靠性的关键。Java提供了丰富的并发数据结构和多线程优化技术,本文将详细介绍常用的并发数据结构及其使用方法......
  • 【数据结构】队列:链表实现
    队列:链表实现结构描述:typedefintDataType;typedefstructQueueNode{DataTypeA;structQueueNode*Next;}Node;classQueueLinked{public://队头、队尾指针Node*Front;Node*Next;//队列操作//把元素X入队voidPush(Dat......
  • 【数据结构】循环队列:链表实现
    循环队列:链表实现结构描述typedefintDataType;typedefstructQueueNode{DataTypeA;structQueueNode*Next;}Node;classQueueCycLinked{public://队头、队尾指针Node*Front;Node*Next;//队列操作//把元素X入队voidPu......
  • 【数据结构】树和二叉树——Lesson1
    Hi~!这里是奋斗的小羊,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎~~......
  • 数据结构之细说链表
    1.1顺序表的问题以及思考经过上一篇顺序表的学习,我们知道顺序表还是有很多缺点顺序表的缺点:1.中间/头部的插入删除,实际复杂度为O(N)2.增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗3.扩容一般是呈两倍增长,势必会有一定的空间浪费。例如当前空间的容量是100,满了......
  • 数据结构——双链表与静态链表
    一、双链表1、定义 双链表:上一篇提到单链表,其实有一个弊端,就是只能单向读取,很笨重并且只能从头指针开始读取,而双链表是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点......
  • 【数据结构】二叉搜索树
    文章目录1.二叉搜索树概念2.二叉搜索树的操作2.1节点与树结构2.2二叉搜索树的查找2.3二叉搜索树的插入2.4二叉搜索树的遍历2.5二叉搜索树的删除(重点)3.二叉搜索树的应用3.1K模型3.2KV模型1.二叉搜索树概念二叉搜索树又称二叉排序树,可以是一棵空树;如果不是空树,则是......
  • 数据结构 day2
    目录思维导图:学习内容:1. 共用体1.1引入目的1.2 定义及初始化1.2.1 概念1.2.2定义格式1.2.3初始化1.2.4变量的大小例子:2. 类型重定义2.1使用方法2.2使用方式(也可以连续定义)2.2.1类型重定义2.2.2  使用方式3.#define与typedef的区别例如:4. ......
  • 基础线段树相关
    权值线段树线段树在这里作为前置知识,我们就不说了,而且权值线段树也不是核心内容,不会大篇幅讲。首先,权值线段树在维护什么?维护的是桶。然后,权值线段树有什么用?可以求一些序列的第\(k\)大之类的问题。于是我们放个板子题。第k小整数简单题,直接看代码和注释就行,当然也可以......