内容简介:线段树首先是一棵树,而且是二叉树。树上的每个节点对应于一个区间[a,b],a,b通常为整数。同一层的节点所代表的区间,互相不重叠。并且同一层的区间加起来是连续的区间,叶子节点的区间是单位长度1,无法再分以上结论为线段树能在O(logn)的时间内完成伪代码
线段树的概念与性质
线段树首先是一棵树,而且是二叉树。树上的每个节点对应于一个区间[a,b],a,b通常为整数。同一层的节点所代表的区间,互相不重叠。并且同一层的区间加起来是连续的区间,叶子节点的区间是单位长度1,无法再分
例如下图表示的是区间[1,9]的线段树
从图上可以看出线段树具有下面几个性质:
- 每个区间的长度是区间内整数的个数
- 叶子节点长度为1,不能再分
- 若一个节点对应的区间是[a,b],则其子节点对应的区间分别是[a,(a+b)/2]和[((a+b)/2)+1,b](除法去尾取整)
- 线段树的评分构造实际上是利用二分的方法,若根节点对应的区间是[a,b],那么他的深度为$log_2(b-a+1)+1$(向上取整)
- 叶子节点的竖拇和根节点表示的区间长度相同
- 线段树节点要么0度,要么2度,因此若叶子节点数目为N,则线段树总节点数目为2N-1
- 线段树上,任意一个区间被分解后得到的“终止节点”数目都是logn量级
- 线段树上更新叶子节点和进行区间分解时间复杂度都是O(logn)的
以上结论为线段树能在O(logn)的时间内完成 插入、更新、查找、统计 数据提供了理论依据
线段树的构建
伪代码
function 以节点idx为根结点,idx对应区间为[l,r] 对节点idx初始化 if(l != r) 以idx的左孩子为根建树,区间为[l,(l+r)>>1] 以idx的右孩子为根建树,区间为[((l+r)>>1)+1,r]
建树的时间复杂度是O(n),n为根节点对应的区间长度
线段树的基本用途
线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分,按区间动态进行修改,而且还需要按区间多次查询,那么使用线段树可以达到较快的速度
线段树应用举例
原题链接: HDU1166
给你一个数列$A_1A_2...A_n$,并且多次进行下列两个操作:
- 对数列里面的某个数进行加减
- 询问这个序列里面任意一个连续的子序列$A_iA_{i+1}...A_j$的和是多少
构建一棵线段树,[1,n]就是根节点对应的区间,在每个节点记录该节点对应的区间内的和sum
对于操作1,因为序列里面$A_i$最多只会被线段树的logn个节点覆盖。只要求对线段树覆盖的$A_i$所在节点的区间进行操作,因此时间复杂度是O(logn)
对于操作2,同样只需要找到区间覆盖的“终止”节点,然后把“终止”节点的sum累加起来,因为这些节点的数量是logn的,所以这一步的复杂度也是O(logn)
走到节点[l,r]时,如果要查询的区间就是[l,r],那么直接返回该节点的sum,并累加到总和上;如果不是,则取mid = (l+r) >> 1,然后看要查询的区间与[l,mid]或[mid+1,r]哪个有交集,就进入哪个区间进行进一步查询
用线段树解题,关键是要想清楚 每个节点要存哪些信息 。先建树,然后插入数据,最后更新、查询
每个节点可表示为一个结构体
class Node { int l, r, sum; }
线段树一般可以由左右指针或数组存储,根节点下标为0,假设线段树某节点为i,则:
- 左子节点下标为(i << 1) + 1
- 右子节点下表为(i << 1) + 2
如果根节点区间为[1,n]
- 使用左右节点指针,则数组需要有2n-1个元素
- 不适用左右节点指针,则数组需要有$2*2^{log_2n}-1$个元素。由于该值小于等于4n-1,因此实际运用时常开4n大小的数组即可
构造初始线段树由根节点一次往下递归构造,代码如下
static void make(int l, int r, int idx) { // l为左端点,r为右端点,idx为数组下标 n[idx].l = l; n[idx].r = r; if (l == r) //已经是叶节点了 n[idx].sum = t[l]; //也可以是t[r] else { make(l,(l + r) >> 1,(idx << 1) + 1); //递归构造左子树 make(((l + r) >> 1) + 1, r, (idx << 1) + 2); //递归构造右子树 n[idx].sum = n[(idx << 1) + 1].sum + n[(idx << 1) + 2].sum; //父节点值等于子节点值之和,线段树分成两段 } }
t数组存放输入的初始值。当总数为n时,执行make(1,n,0),输入样例得到的额线段树如下图所示
当第idx个营地增加j个人时,从根节点n[0]开始,不断往下递归更改人数,即只要包含改点idx的线段都增加相应的人数j,代码如下
static void add(int i, int j, int idx) { // 第i个营地增加j个人 // 从根节点不断往下更改,只要包含点i的线段都增加数量j n[idx].sum += j; if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止 return; if (i <= ((n[idx].l + n[idx].r) >> 1)) // 如果i在线段左边 add(i, j, (idx << 1) + 1); // 递归进入左子节点 else // 如果i在线段右边 add(i, j, (idx << 1) + 2); // 递归进入右子节点 }
同理,当第i个营地减少j个人时,代码如下
static void sub(int i, int j, int idx) { // 第i个营地减少j个人 // 从根节点不断往下更改,只要包含点i的线段都减少数量j n[idx].sum -= j; if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止 return; if (i <= ((n[idx].l + n[idx].r) >> 1)) //如果i在线段左边 sub(i, j, (idx << 1) + 1); // 递归进入左子节点 else sub(i, j, (idx << 1) + 2); // 递归进入右子节点 }
询问从[l,r]区间内的营地人数代码如下
static void query(int l, int r, int idx) { // 初始idx为0,即从根节点开始查找 if (l <= n[idx].l && r >= n[idx].r) SUM += n[idx].sum; else { int mid = (n[idx].l + n[idx].r) >> 1; if (r <= mid) // 要查询的区间在左边 query(l, r, (idx << 1) + 1); else if (l > mid) // 要查询的区间在右边 query(l, r, (idx << 1) + 2); else { // 要查询的区间在中间,分段查询,左右都查 query(l, r, (idx << 1) + 1); query(l, r, (idx << 1) + 2); } } }
完整代码如下
import java.util.Scanner; public class Main { static Node[] n; static int[] t; static int SUM; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int T = cin.nextInt(); for (int p = 1; p <= T; p++) { int tmp = 0; int N = cin.nextInt(); n = new Node[4 * N]; t = new int[N + 1]; for (int i = 1; i <= N; i++) t[i] = cin.nextInt(); make(1, N, 0); while (true) { String str = cin.next(); if ("End".equals(str)) break; int i = cin.nextInt(); int j = cin.nextInt(); if ("Query".equals(str)) { SUM = 0; if (tmp == 0) { System.out.println("Case " + p + ":"); tmp++; } query(i, j, 0); System.out.println(SUM); } else if ("Add".equals(str)) add(i, j, 0); else // Sub sub(i, j, 0); } } } static void make(int l, int r, int idx) { // l为左端点,r为右端点,idx为数组下标 n[idx] = new Node(); n[idx].l = l; n[idx].r = r; if (l == r) // 已经是叶节点了 n[idx].sum = t[l]; // 也可以是t[r] else { make(l, (l + r) >> 1, (idx << 1) + 1); // 递归构造左子树 make(((l + r) >> 1) + 1, r, (idx << 1) + 2); // 递归构造右子树 n[idx].sum = n[(idx << 1) + 1].sum + n[(idx << 1) + 2].sum; // 父节点值等于子节点值之和,线段树分成两段 } } static void add(int i, int j, int idx) { // 第i个营地增加j个人 // 从根节点不断往下更改,只要包含点i的线段都增加数量j n[idx].sum += j; if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止 return; if (i <= ((n[idx].l + n[idx].r) >> 1)) // 如果i在线段左边 add(i, j, (idx << 1) + 1); // 递归进入左子节点 else // 如果i在线段右边 add(i, j, (idx << 1) + 2); // 递归进入右子节点 } static void sub(int i, int j, int idx) { // 第i个营地减少j个人 // 从根节点不断往下更改,只要包含点i的线段都减少数量j n[idx].sum -= j; if (n[idx].l == i && n[idx].r == i) // 如果找到i的叶子节点则停止 return; if (i <= ((n[idx].l + n[idx].r) >> 1)) // 如果i在线段左边 sub(i, j, (idx << 1) + 1); // 递归进入左子节点 else sub(i, j, (idx << 1) + 2); // 递归进入右子节点 } static void query(int l, int r, int idx) { // 初始idx为0,即从根节点开始查找 if (l <= n[idx].l && r >= n[idx].r) SUM += n[idx].sum; else { int mid = (n[idx].l + n[idx].r) >> 1; if (r <= mid) // 要查询的区间在左边 query(l, r, (idx << 1) + 1); else if (l > mid) // 要查询的区间在右边 query(l, r, (idx << 1) + 2); else { // 要查询的区间在中间,分段查询,左右都查 query(l, r, (idx << 1) + 1); query(l, r, (idx << 1) + 2); } } } } class Node { int l, r, sum; }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。