线段树题目

适合非递归线段树的题目:

Codeforces 612D The Union of k-Segments :  题解
题意:线段求交,给定一堆线段,按序输出被覆盖k次或以上的线段和点。
基础题,先操作,最后一次下推标记,然后输出,
维护两个线段树,一个线段覆盖,一个点覆盖。

Codeforces 35E Parade : 题解

题意:给定若干矩形,下端挨着地面,求最后的轮廓形成的折线,要求输出每一点的坐标。

思路:虽然是区间修改的线段树,但只需要在操作结束后一次下推标记,然后输出,所以适合非递归线段树。

URAL 1846 GCD2010 :  题解

题意:总共10万个操作,每次向集合中加入或删除一个数,求集合的最大公因数。(规定空集的最大公因数为1)

Codeforces 12D Ball :   题解

题意:

给N (N<=500000)个点,每个点有x,y,z ( 0<= x,y,z <=10^9 )

对于某点(x,y,z),若存在一点(x1,y1,z1)使得x1 > x && y1 > y && z1 > z 则点(x,y,z)是特殊点。

问N个点中,有多少个特殊点。

提示:排序+线段树

Codeforces 19D Points : 题解

 

题意:

给定最多20万个操作,共3种:

1.add x y         :加入(x,y)这个点

2.remove x y  :删除(x,y)这个点

3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

提示:排序,线段树套平衡树

Codeforces 633E Startup Funding : 题解

这题需要用到一点概率论,组合数学知识,和二分法。

非递归线段树在这题中主要解决RMQ问题(区间最大最小值问题),由于不带修改,这题用Sparse Table求解RMQ是标答。

因为RMQ询问是在二分法之内求的,而Sparse Table可以做到O(1)查询,所以用Sparse Table比较好,总复杂度O(n*log(n))。

不过非递归线段树也算比较快的了,虽然复杂度是O(n*log(n)*log(n)),还是勉强过了这题。

扫描线题目:

 

POJ 1177 Picture:给定若干矩形求合并之后的图形周长    题解
HDU 1255 覆盖的面积:给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.   题解
HDU 3642 Get The Treasury:给定若干空间立方体,求重叠了3次或以上的体积(这个是扫描面,每个面再扫描线)题解
POJ 2482 Stars in your window : 给定一些星星的位置和亮度,求用W*H的矩形能够框住的星星亮度之和最大为多少。  题解

递归线段树题目:

Codeforces 558E A Simple Task  题解给定一个长度不超过10^5的字符串(小写英文字母),和不超过5000个操作。

每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。

最后输出最终的字符串。

Codeforces 527C Glass Carving  :  题解
给定一个矩形,不停地纵向或横向切割,问每次切割后,最大的矩形面积是多少。
URAL1989 Subpalindromes    题解
给定一个字符串(长度<=100000),有10万个操作。
操作有两种:
1:改变某个字符。
2:判断某个子串是否构成回文串。
HDU 4288 Coder :  题解
 题意:对一个集合进行插入与删除操作。要求询问某个时刻,集合中的元素从小到大排序之后,序号%5 ==3 的元素值之和。
这题其实不一定要用线段树去做的,不过线段树还是可以做的。
HDU 2795 BillBoard : 题解

题意:有一个板,h行,每行w长度的位置。每次往上面贴一张海报,长度为1*wi .

每次贴的时候,需要找到最上面的,可以容纳的空间,并且靠边贴。

Codeforces 374D Inna and Sequence :题解
题意:给定百万个数a[m],然后有百万个操作,每次给现有序列加一个字符(0或1),或者删掉已有序列中,第 a[0] 个,第a[1]个,...,第a[m]个。
Codeforces 482B Interesting Array:  题解

题意就是,给定n,m.

满足m个条件的n个数,或说明不存在。

每个条件的形式是,给定 Li,Ri,Qi ,要求   a[Li]&a[Li+1]&...&a[Ri] = Qi ;

Codeforces 474E Pillar (线段树+动态规划):  题解

题意就是,给定10^5 个数(范围10^15),求最长子序列使得相邻两个数的差大于等于 d。

POJ 2777  Count Color :   题解

给线段涂颜色,最多30种颜色,10万个操作。

每个操作给线段涂色,或问某一段线段有多少种颜色。

30种颜色用int的最低30位来存,然后线段树解决。

URAL 1019 Line Painting: 线段树的区间合并  题解

给一段线段进行黑白涂色,最后问最长的一段白色线段的长度。

Codeforces 633H Fibonacci-ish II  :题解

这题需要用到莫队算法(Mo's Algorithm)+线段树区间修改,不过是单边界的区间,写起来挺有趣。

另一种解法就是暴力,很巧妙的方法,高复杂度+低常数居然就这么给过了。

树套树题目:

ZOJ 2112 Dynamic Rankings 动态区间第k大  题解
做法:树状数组套主席树 或者 线段树套平衡树
Codeforces 605D Board Game :  题解
做法:广度优先搜索(BFS)  +  线段树套平衡树

Codeforces 19D Points : 题解

 

题意:

给定最多20万个操作,共3种:

1.add x y         :加入(x,y)这个点

2.remove x y  :删除(x,y)这个点

3.find x y         :找到在(x,y)这点右上方的x最小的点,若x相同找y最小的点,输出这点坐标,若没有,则输出-1.

提示:排序,线段树套平衡树

一步一步理解线段树

摘自http://www.cnblogs.com/TenosDoIt/p/3453089.html


一 概述

线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。

线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。

二 从一个例子理解线段树

下面我们从一个经典的例子来了解线段树,问题描述如下:从数组arr[0...n-1]中查找某个数组某个区间内的最小值,其中数组大小固定,但是数组中的元素的值可以随时更新。

对这个问题一个简单的解法是:遍历数组区间找到最小值,时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大,而查询操作很频繁的时候,耗时可能会不满足需求。

另一种解法:使用一个二维数组来保存提前计算好的区间[i,j]内的最小值,那么预处理时间为O(n^2),查询耗时O(1), 但是需要额外的O(n^2)空间,当数据量很大时,这个空间消耗是庞大的,而且当改变了数组中的某一个值时,更新二维数组中的最小值也很麻烦。

我们可以用线段树来解决这个问题:预处理耗时O(n),查询、更新操作O(logn),需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

叶子节点是原始组数arr中的元素
非叶子节点代表它的所有子孙叶子节点所在区间的最小值
例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树(背景为白色表示叶子节点,非叶子节点的值是其对应数组区间内的最小值,例如根节点表示数组区间arr[0...5]内的最小值是1): 本文地址

由于线段树的父节点区间是平均分割到左右子树,因此线段树是完全二叉树,对于包含n个叶子节点的完全二叉树,它一定有n-1个非叶节点,总共2n-1个节点,因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作:创建线段树、查询、节点更新 是如何运作的呢(以下所有代码都是针对求区间最小值问题)?

2.1 创建线段树

对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树,我们也可以用数组来存储,下面的讨论及代码都是数组来存储线段树,节点结构如下(注意到用数组存储时,有效空间为2n-1,实际空间确不止这么多,比如上面的线段树中叶子节点1、3虽然没有左右子树,但是的确占用了数组空间,实际空间是满二叉树的节点数目: , 是树的高度,但是这个空间复杂度也是O(n)的 )。

struct SegTreeNode{int val;};

定义包含n个节点的线段树 SegTreeNode segTree[n],segTree[0]表示根节点。那么对于节点segTree[i],它的左孩子是segTree[2i+1],右孩子是segTree[2i+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);
    }
}

2.2 查询线段树

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

/*
功能:线段树的区间查询
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。

2.3单节点更新

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

/*
功能:更新线段树中某个叶子节点的值
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的值更新后不变,根节点更新后也不变。

2.4 区间更新

区间更新是指更新某个区间内的叶子节点的值,因为涉及到的叶子节点不止一个,而叶子节点会影响其相应的非叶父节点,那么回溯需要更新的非叶子节点也会有很多,如果一次性更新完,操作的时间复杂度肯定不是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]),就相当于单节点更新,单节点更新只是区间更新的特例。

三 线段树实战

求区间的最大值、区间求和等问题都是采用类似上面的延迟标记域。下面会通过acm的一些题目来运用一下线段树。

等待更新......

参考资料

GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

懂得博客[数据结构之线段树]:http://dongxicheng.org/structure/segment-tree/

MetaSeed[数据结构专题—线段树]: http://blog.csdn.net/metalseed/article/details/8039326

NotOnlySuccess[完全版 线段树]: http://www.notonlysuccess.com/index.php/segment-tree-complete/

主席树

主席树又称函数式线段树,就是通过函数来实现的线段树,可以处理一些神奇的问题。

【例题】K-th Number

  • 很明显,这题的数据是不允许对于每一个询问进行一次排序的。那么,考虑一种解法,建你n棵线段树,第i棵线段树维护的是1~i中,大小属于[1,m]的数的数量(1 <= m <= max)。对于每次询问的L,R区间中的第k小数,便可以通过log(n)的时间来完成。
  • 显然我们不能直接全部建出来, 这样时空复杂度都不允许。我们发现相邻的两棵线段树的差别只是i比i-1多了a[i]这个数, 而在权值线段树中多出这样一个值, 第 i 棵树
    与第 i -1棵树的差别实际上只有log 个节点。 也就是我们可以看做在第 i -1
    棵权值线段树中插入权值a[i] 得到第 i 棵权值线段树, 而单点插入过程中只会遇到以及修改根到那个叶子路径上的log(n)个节点。
  • 假设我们已经得到了第 i -1棵权值线段树, 现在要在第i -1棵的基础上加入权值
    a[i]来得到第i 棵树。 首先我们新建一个节点来表示第i 棵树的根节点, 接着我们从第i -1棵以及第i棵树的根节点开始考虑。 对于当前节点, 若当前插入的值a[i] 在当前权值区间中的左半部分,说明a[i] 它要影响第 i 棵树当前节点的左子树的值, 则我们新建一个左儿子, 作为第 i 棵树对应的当前节点左儿子; 而第i 棵树对应的当前节点右儿子( 子树) , 它( 们) 并不受新插入的值的影响, 因此它与第 i -1棵树的当前节点的右儿子( 子树) 的信息一模一样, 所以我们考虑直接将第 i 棵树对应的当前节点右儿子设为第i -1棵树的当前节点的右儿子。 反之亦然。
    插入的代码如下:

    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void add(int &cnt, int last, int l, int r, int v)  {
        cnt = ++tot;
        tr[cnt] = tr[last];
        tr[cnt].sum++;
        if (l < r)  {
            if (v <= (l + r) / 2) add(tr[cnt].ls, tr[last].ls, l, (l + r) / 2, v);
            else add(tr[cnt].rs, tr[last].rs, (l + r) / 2 + 1, r, v);
        }
    }

那么对于每一个询问,代码就显而易见了:


1
2
3
4
5
6
7
int que(int pas, int now, int l, int r, int k)  {
    if (l == r) return l;
    int s = tr[tr[now].ls].sum - tr[tr[pas].ls].sum;
    if (k <= s) return que(tr[pas].ls, tr[now].ls, l, (l + r) / 2, k);
    return que(tr[pas].rs, tr[now].rs, (l + r) / 2 + 1, r, k - s);

}

具体代码如下:

继续阅读主席树

小白逛公园

小白逛公园

区间查询,单点修改,使用线段树。

维护四个值:Lmax表示必取左端点的最大子段和,Rmax表示必取左端点的最大子段和,max表示整个区间的最大子段和,sum表示区间和。

对于修改操作,直接递归修改,然后update所有路径上的节点。

对于查询操作,维护两个值:A表示以当前区间作为结尾的子段和最大值,B表示不以当前区间作为结尾的子段和最大值。答案即为每次修改A,B时的max(A,B)。

注意本题查询操作的a,b没有确定的大小关系。

还有应正确理解变量含义且不要打错变量(调试了2h+真的气)。

更好的题解以及有关题目解析

继续阅读小白逛公园

BZOJ3224 Tyvj1728 普通平衡树

BZOJ3224

Tyvj1728

本题可以使用平衡树,线段树,甚至std::vector通过。

splay的话直接做就可以了。

对于1操作,直接插,注意无需重复插入同一数字,用cnt数组统计数字出现次数即可。

对于2操作,先将要删的点splay至根节点,然后分4种情况。1.若根节点的cnt值大于1,将其-1;2.若根节点的cnt值等于1且无左右子节点,清空整棵树;3.若根节点的cnt值等于1且左右子节点无其中一个,将根结点一直另一子节点;4.若根节点的cnt值等于1且左右子节点都存在,找出根节点的前驱,将其splay至根节点,即可删除原来的根节点。注意在2,3,4情况时处理好父子节点的关系。

对于3,4,5,6操作,应用类似普通二叉查找树的方法即可。注意在5,6操作中可能存在查询不在树中的数字。

继续阅读BZOJ3224 Tyvj1728 普通平衡树