1. 首页
  2. 文章中心
  3. 数据结构/算法/Leetcode

poj3468-线段树详解

62 阅读 0 评论
我是靠谱客的博主 碧蓝钥匙，最近开发中收集的这篇文章主要介绍poj3468-线段树详解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

什么是线段树

线段树，是一种树形结构，它的各个节点都保存的是一条线段。线段树主要是解决动态查询的问题，使用二叉树的结构后，它的操作基本的复杂度为O(logn).

线段树的每个节点表示一个区间，其左右子树表示该节点的左半区间和右半区间。比如说，一个节点为[a, b],中间的值为c=(a+b)/2,左子节点表示的区间为[a,c],右子节点表示的区间为[c+1, b]

线段树要解决的问题

问题描述：在一个数组arr[0…n-1]中，查找某个区间[a,b]上的最小值，其中数组的大小固定，但是数组中的元素可以更新。
如果使用遍历数组的方法，时间复杂度为O(n),空间复杂度为O(1).当数据量很大时，不可取。如果用一个二维数组来提前计算好区间[i,j]的最小值，那么预处理时间复杂度为O(n^2),空间复杂度也为O(n^2)。

我们可以用线段树解决这个问题：预处理时间为O(n),查询和更新操作为O(log(n)),需要的额外空间为O(n).为此我们构建一个二叉树：

  • 叶子节点是数组中的元素
  • 非叶子节点表示其所有子节点的最小值

比如对于一个数组[2,5,1,4,9,3]构造的二叉树为：

由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点，因此存储线段是需要的空间复杂度是O(n)。

操作

创建线段树

线段树可以直接使用数组存储。节点的结构为：

struct SegTreeNode
{
int val;
}

定义包含n个节点的线段树 SegTreeNode segTree[n]，segTree[0]表示根节点。那么对于节点segTree[i]，它的左孩子是segTree[2*i+1],右孩子是segTree[2*i+2]。

我们可以从根节点开始，平分区间，递归的创建线段树，线段树的创建函数如下：

const int MAXNUM = 1000;
struct SegTreeNode
{
int val;
}segTree[MAXNUM];//定义线段树
/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
if(istart == iend)//叶子节点
segTree[root].val = arr[istart];
else
{
int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//递归构造左子树
build(root*2+2, arr, mid+1, iend);//递归构造右子树
//根据左右子树根节点的值，更新当前根节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}

查询线段树

已经构建好了线段树，那么怎样在它上面超找某个区间的最小值呢？查询的思想是选出一些区间，使他们相连后恰好涵盖整个查询区间，因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下，具体见代码解释

/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
//查询区间和当前节点区间没有交集
if(qstart > nend || qend < nstart)
return INFINITE;
//当前节点区间包含在查询区间内
if(qstart <= nstart && qend >= nend)
return segTree[root].val;
//分别从左右子树查询，返回两者查询结果的较小值
int mid = (nstart + nend) / 2;
return min(query(root*2+1, nstart, mid, qstart, qend),
query(root*2+2, mid + 1, nend, qstart, qend));

}

举例说明（对照上面的二叉树）：

1、当我们要查询区间[0,2]的最小值时，从根节点开始，要分别查询左右子树，查询左子树时节点区间[0,2]包含在查询区间[0,2]内，返回当前节点的值1，查询右子树时，节点区间[3,5]和查询区间[0,2]没有交集，返回正无穷INFINITE，查询结果取两子树查询结果的较小值1，因此结果是1.

2、查询区间[0,3]时，从根节点开始，查询左子树的节点区间[0,2]包含在区间[0,3]内，返回当前节点的值1；查询右子树时，继续递归查询右子树的左右子树，查询到非叶节点4时，又要继续递归查询：叶子节点4的节点区间[3,3]包含在查询区间[0,3]内，返回4，叶子节点9的节点区间[4,4]和[0,3]没有交集，返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4，叶子节点3的节点区间[5,5]和[0,3]没有交集，返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。

单节点更新

单节点更新是指只更新线段树的某个叶子节点的值，但是更新叶子节点会对其父节点的值产生影响，因此更新子节点后，要回溯更新其父节点的值。

/*
功能：更新线段树中某个叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
index: 待更新节点在原始数组arr中的下标
addVal: 更新的值（原来的值加上addVal）
*/
void updateOne(int root, int nstart, int nend, int index, int addVal)
{
if(nstart == nend)
{
if(index == nstart)//找到了相应的节点，更新之
segTree[root].val += addVal;
return;
}
int mid = (nstart + nend) / 2;
if(index <= mid)//在左子树中更新
updateOne(root*2+1, nstart, mid, index, addVal);
else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新
//根据左右子树的值回溯更新当前节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}

比如我们要更新叶子节点4（addVal = 6）,更新后值变为10，那么其父节点的值从4变为9，非叶结点3的值更新后不变，根节点更新后也不变。

区间更新

区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其相应的非叶父节点，那么回溯需要更新的非叶子节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不是O(lgn)，例如当我们要更新区间[0,3]内的叶子节点时，需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念，这也是线段树的精华所在。

延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。

因此需要在线段树结构中加入延迟标记域，本文例子中我们加入标记与addMark，表示节点的子孙节点在原来的值的基础上加上addMark的值，同时还需要修改创建函数build 和 查询函数 query，其中区间更新的函数为update，代码如下：

const int INFINITE = INT_MAX;
const int MAXNUM = 1000;
struct SegTreeNode
{
int val;
int addMark;//延迟标记
}segTree[MAXNUM];//定义线段树
/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
segTree[root].addMark = 0;//----设置标延迟记域
if(istart == iend)//叶子节点
segTree[root].val = arr[istart];
else
{
int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//递归构造左子树
build(root*2+2, arr, mid+1, iend);//递归构造右子树
//根据左右子树根节点的值，更新当前根节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}
/*
功能：当前节点的标志域向孩子节点传递
root: 当前线段树的根节点下标
*/
void pushDown(int root)
{
if(segTree[root].addMark != 0)
{
//设置左右孩子节点的标志域，因为孩子节点可能被多次延迟标记又没有向下传递
//所以是 “+=”
segTree[root*2+1].addMark += segTree[root].addMark;
segTree[root*2+2].addMark += segTree[root].addMark;
//根据标志域设置孩子节点的值。因为我们是求区间最小值，因此当区间内每个元
//素加上一个值时，区间的最小值也加上这个值
segTree[root*2+1].val += segTree[root].addMark;
segTree[root*2+2].val += segTree[root].addMark;
//传递后，当前节点标记域清空
segTree[root].addMark = 0;
}
}
/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
//查询区间和当前节点区间没有交集
if(qstart > nend || qend < nstart)
return INFINITE;
//当前节点区间包含在查询区间内
if(qstart <= nstart && qend >= nend)
return segTree[root].val;
//分别从左右子树查询，返回两者查询结果的较小值
pushDown(root); //----延迟标志域向下传递
int mid = (nstart + nend) / 2;
return min(query(root*2+1, nstart, mid, qstart, qend),
query(root*2+2, mid + 1, nend, qstart, qend));
}
/*
功能：更新线段树中某个区间内叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[ustart, uend]: 待更新的区间
addVal: 更新的值（原来的值加上addVal）
*/
void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
{
//更新区间和当前节点区间没有交集
if(ustart > nend || uend < nstart)
return ;
//当前节点区间包含在更新区间内
if(ustart <= nstart && uend >= nend)
{
segTree[root].addMark += addVal;
segTree[root].val += addVal;
return ;
}
pushDown(root); //延迟标记向下传递
//更新左右孩子节点
int mid = (nstart + nend) / 2;
update(root*2+1, nstart, mid, ustart, uend, addVal);
update(root*2+2, mid+1, nend, ustart, uend, addVal);
//根据左右子树的值回溯更新当前节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}

区间更新举例说明：当我们要对区间[0,2]的叶子节点增加2，利用区间查询的方法从根节点开始找到了非叶子节点[0-2]，把它的值设置为1+2 = 3，并且把它的延迟标记设置为2，更新完毕；当我们要查询区间[0,1]内的最小值时，查找到区间[0,2]时，发现它的标记不为0，并且还要向下搜索，因此要把标记向下传递，把节点[0-1]的值设置为2+2 = 4，标记设置为2，节点[2-2]的值设置为1+2 = 3，标记设置为2（其实叶子节点的标志是不起作用的，这里是为了操作的一致性），然后返回查询结果：[0-1]节点的值4；当我们再次更新区间[0,1]（增加3）时，查询到节点[0-1],发现它的标记值为2，因此把它的标记值设置为2+3 = 5，节点的值设置为4+3 = 7；

其实当区间更新的区间左右值相等时（[i,i]），就相当于单节点更新，单节点更新只是区间更新的特例。

例题poj3468

/*
poj 3468-线段树
http://poj.org/problem?id=3468
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations.
One type of operation is to add some given number to each number in a given interval.
The other is to ask for the sum of numbers in a given interval.
题目大意：对于给定的一组数，有两种操作：求某个区间的和以及更新某个区间的值
解题思路：用线段树。
*/
#include <cstdio>
#include <algorithm>
using namespace std;
//#pragma warning(disable:4996)
#define ll long long
inline int L(int r)
{
return r << 1;
}
inline int R(int r)
{
return (r << 1) + 1;
}
inline int MID(int l, int r)
{
return (l + r) >> 1;
}
const int max_n = 1e5 + 10;
ll sum;
//树的节点结构：线段的起点left和重点right
//[left, right]的和以及更新值add
struct node
{
int left;
int right;
ll val;
ll add;
}tree[max_n<<2];//interval tree
ll arr[max_n << 2];//init array
//建一棵树
void Built(int l, int r, int root)
{
tree[root].left = l;
tree[root].right = r;
tree[root].add = 0;
if (l == r)
{
tree[root].val = arr[l];
return;
}
else
{
//递归构建左右子树
int mid = MID(l, r);
Built(l, mid, L(root));
Built(mid + 1, r, R(root));
//更新root
tree[root].val = tree[L(root)].val + tree[R(root)].val;
}
}
void Update(int root)
{
//更新子树
if (tree[root].add)
{
tree[L(root)].add += tree[root].add;//
tree[R(root)].add += tree[root].add;//
tree[L(root)].val += (tree[L(root)].right - tree[L(root)].left + 1)*tree[root].add;
tree[R(root)].val += (tree[R(root)].right - tree[R(root)].left + 1)*tree[root].add;
tree[root].add = 0;
}
}
//加上v
void Add(int l, int r, ll v, int root)
{
if (l <= tree[root].left && r >= tree[root].right)
{
tree[root].add += v;
tree[root].val += v*(tree[root].right - tree[root].left + 1);
return;
}
else
{
//分别在左右子树上增加
Update(root);
if (tree[root].left == tree[root].right)
return;
int mid = MID(tree[root].left, tree[root].right);
if (l > mid)
Add(l, r, v, R(root));
else if (r <= mid)
Add(l, r, v, L(root));
else
{
Add(l, mid, v, L(root));
Add(mid + 1, r, v, R(root));
}
tree[root].val = tree[L(root)].val + tree[R(root)].val;
}
}
void Solve(int l, int r, int root)
{
if (l <= tree[root].left && r >= tree[root].right)
{
sum += tree[root].val;
return;
}
else {
Update(root);
if (tree[root].left == tree[root].right)
return;
int mid = MID(tree[root].left, tree[root].right);
if (l > mid)
Solve(l, r, R(root));
else if (r <= mid)
Solve(l, r, L(root));
else
{
Solve(l, mid, L(root));
Solve(mid + 1, r, R(root));
}
}
}
int main()
{
//freopen("poj3468.txt", "r", stdin);
int m, n;
while (scanf("%d %d", &m, &n) != EOF)
{
for (int i = 1; i <= m; ++i)
scanf("%lld", arr + i);
//建树
Built(1, m, 1);
char c[2];
while (n--)
{
scanf("%s", c);
if ('C' == c[0])
{
int l, f;
ll v;
scanf("%d %d %lld", &l, &f, &v);
Add(l, f, v, 1);
}
else
{
int l, f;
scanf("%d %d", &l, &f);
sum = 0;
Solve(l, f, 1);
printf("%lldn", sum);
}
}
}
}

参考

[1]http://www.cnblogs.com/TenosDoIt/p/3453089.html
[2]http://www.cppblog.com/cxiaojia/archive/2011/11/22/poj3468.html

最后

以上就是碧蓝钥匙为你收集整理的poj3468-线段树详解的全部内容，希望文章能够帮你解决poj3468-线段树详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(41)

相关文章

POJ3468树状数组
POJ3468树状数组
POJ3468(用lazy标记进行延迟更新)
POJ3468(用lazy标记进行延迟更新)
poj3468(lazy标记）
poj3468(lazy标记）
线段树POJ3468(成段更新，区间求和)
线段树POJ3468(成段更新，区间求和)
poj3468-线段树详解
poj3468-线段树详解
Splay POJ3468（老题新做）
Splay POJ3468（老题新做）
（线段树）hdoj1166-敌兵布阵
（线段树）hdoj1166-敌兵布阵
HDOJ4027-线段树
HDOJ4027-线段树

评论列表共有 0 条评论

立即
投稿
返回
顶部