wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共6篇）

ST表与树状数组

ST表　st表可以解决区间最值的问题。可以做到O(nlogn)预处理，O（1）查询，但是不支持修改。　　st表的大概思路就是用st[i][j]来表示从i开始的2的j次方个树中的最值，查询时就从左端点开始，找到区间长度是2的多少次方，然后进行查询。然而，很明显，我们要查询的区间长度不一定是...

数据结构

2018-05-04

0 409

单调队列

　单调队列就是维护一个队列，使得该队列从队首到队尾成单调递增或是单调递减。　做法就是每向队列里加入一个元素就判断该元素是不是比队尾元素大（以递减序列为例），是的话就将队尾元素出列，直到该元素比队尾元素小，然后将该元素放置队尾。　　这么久了一直不明白单调队列的实现，现在看来，原来这么简单。。。...

数据结构

2018-08-04

0 471

树链剖分&dfs序

树上问题　　很多处理区间的问题（像是RMQ，区间修改）。可以用线段树，树状数组，ST表这些数据结构来维护。但是如果将这些问题挪到了树上，就不能直接用这些数据结构来处理了。这时就用到了dfs序和树链剖分。 DFS序　　dfs序就是按照dfs的顺序对一棵树上的结点进行编号。这样完成编号的优点是...

数据结构

2018-08-06

0 407

ST表与树状数组

ST表　st表可以解决区间最值的问题。可以做到O(nlogn)预处理，O（1）查询，但是不支持修改。　　st表的大概思路就是用st[i][j]来表示从i开始的2的j次方个树中的最值，查询时就从左端点开始，找到区间长度是2的多少次方，然后进行查询。然而，很明显，我们要查询的区间长度不一定是...

数据结构

2018-05-04

0 401

单调队列

　单调队列就是维护一个队列，使得该队列从队首到队尾成单调递增或是单调递减。　做法就是每向队列里加入一个元素就判断该元素是不是比队尾元素大（以递减序列为例），是的话就将队尾元素出列，直到该元素比队尾元素小，然后将该元素放置队尾。　　这么久了一直不明白单调队列的实现，现在看来，原来这么简单。。。...

数据结构

2018-08-04

0 394

树链剖分&dfs序

树上问题　　很多处理区间的问题（像是RMQ，区间修改）。可以用线段树，树状数组，ST表这些数据结构来维护。但是如果将这些问题挪到了树上，就不能直接用这些数据结构来处理了。这时就用到了dfs序和树链剖分。 DFS序　　dfs序就是按照dfs的顺序对一棵树上的结点进行编号。这样完成编号的优点是...

数据结构

2018-08-06

0 540