分类:数据结构
平衡树(Treap)
惊!竟然没有Treap的博文!!
https://www.cnblogs.com/Thm-V/p/11297556.html
BZOJ1483 [HNOI2009] 梦幻布丁
链表+启发式合并
懒得写链表
std::set代替链表
首先算出初始状态答案
然后对于每个修改操作,启发式合并两种颜色。
启发式合并:在合并两个集合(或两棵树)时,暴力将较小集合的元素(或结点更少的树的所有节点)合并(或插入)到另一较大集合(或结点更多的树)中。
简单来说就是弱肉强食。
而且启发式合并的时间复杂度可以证明是O(logn)的
对于本题,枚举较小的集合的每个元素,处理答案并且加入较大的集合,同时更改颜色。
对于查询操作,由于每次修改同时都计算出答案,直接输出即可。
可持久化线段树/主席树入门
在wmf大佬怂恿
一天学习一个数据结构每天划水下,大概理清可持久化线段树,又名主席树的大致思路和代码实现。今天JZ的雨,下得更加的猛烈了QAQ
【可持久化数据结构初步】
先来一波可持久化线段树,又名主席树。在可持久化数据结构中,能够支持查询历史版本的数据。是对原数据结构的进一步加深与理解,代码和原理也只能算是锦上添花。借用某大犇的话讲就是,“主席树难不是在于它自身,而是难在于如何把一道题跟它扯上关系”
下面进入正题:
在某些题目中,我们可能需要不断地对线段树修改,并且有可能需要查询的是某一次修改前的事情,而在线段树中,修改即意味着是数据丢失,是难以查询到从前的东西。而可持久化的基本理念就是不将其修改,而是扩建。
初步的想法是对于一次修改就重新搞一棵树出来,但是这在空间上是极度不允许的。我们能够联想到,对于一次修改,复杂度是log(n)级别的,这说明了一次修改所涉及到的区间只有log(n)个,故我们没有必要每次完整地建一棵线段树,只需要新建log(n)个被修改的区间,其他的未被操刀过的区间借用前者的区间即可。每一次修改扩建log(n)个,这是能够勉强接受的。
在此顺便注一句:一定要计算好空间!!!不要像我一样空间算错了开太小然后查了一小时错都没查出来!!!!!!!!后来跟标程一字一字进行了一场“代码优先性逐行逐字比较型工程”才发现标程空间比我多了一点点......
【代码环节】
例题:洛谷P3834
这是我阅览了十多份代码中,风格最为人性化的一种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67 #include<cstdio>
#include<algorithm>
#include<iostream>
#define mid (l+r)/2
#define N 200005
using namespace std;
struct node
{
int val,id;
};
struct chariman
{
int l,r;
int sum;
}tree[N*20];
bool cmp(node aa,node bb)
{
return aa.val<bb.val;
}
int n,q,a[N],root[N],cnt;
node b[N];
void updata(int &st,int l,int r,int p)
{
tree[++cnt]=tree[st];
st=cnt;
tree[st].sum++;
if (l==r) return;
if (p<=mid) updata(tree[st].l,l,mid,p);
else updata(tree[st].r,mid+1,r,p);
return;
}
int query(int i,int j,int k,int l,int r)
{
if (l==r) return l;
int ltot=tree[tree[j].l].sum-tree[tree[i].l].sum;
if (k<=ltot) return query(tree[i].l,tree[j].l,k,l,mid);
else return query(tree[i].r,tree[j].r,k-ltot,mid+1,r);
}
int main()
{
scanf("%d %d",&n,&q);
for (int i=1; i<=n; i++)
{
scanf("%d",&b[i].val);b[i].id=i;
}
sort(b+1,b+1+n,cmp);
for (int i=1; i<=n; i++) a[b[i].id]=i;
for (int i=1; i<=n; i++)
{
root[i]=root[i-1];
updata(root[i],1,n,a[i]);
}
int x,y,k;
while (q--)
{
scanf("%d %d %d",&x,&y,&k);
printf("%d\n",b[query(root[x-1],root[y],k,1,n)].val);
}
return 0;
}
【PAUSE】
【2018.8.8】JZ集训倒数第13天
又是风(yin)和(qing)日(bu)丽(ding)的美好的一天JZ生活呢 ^.^
-
CF916E Jamie and Tree
线段树从零开始 By 岩之痕
https://blog.csdn.net/zearot/article/details/52280189
线段树题目
适合非递归线段树的题目:
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)),还是勉强过了这题。
扫描线题目:
递归线段树题目:
每个操作 L R K 表示给区间[L,R]的字符串排序,K=1为升序,K=0为降序。
最后输出最终的字符串。
题意:有一个板,h行,每行w长度的位置。每次往上面贴一张海报,长度为1*wi .
每次贴的时候,需要找到最上面的,可以容纳的空间,并且靠边贴。
题意就是,给定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)+线段树区间修改,不过是单边界的区间,写起来挺有趣。
另一种解法就是暴力,很巧妙的方法,高复杂度+低常数居然就这么给过了。
树套树题目:
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/