Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共7篇）

树链剖分详解

预备知识：线段树，DFS序 DFS序 DFS序，字面意思，就是DFS到的顺序我们只需要在搜到节点的时候记录一下就可以了比如这样可能是一个树的DFS序那知道了DFS序又有什么用呢我们可以发现一颗子树在DFS序上是连续的一段那么它就有了一个区间的性质，每个节点对应一...

数据结构树链剖分

2018-12-27

0 524

二叉搜索树（BST）详解

前言：平衡树的前置知识吧二叉搜索树的定义：二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根节点的值；（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；（3）左、右子树也分别为二叉搜索树； ...

数据结构

2019-01-24

0 783

普通Splay详解

预备知识：二叉搜索树（BST）至于BST，随便看一下就可以，我们知道二叉搜索树是O(logN)的，那我们为什么要用平衡树呢？之前我们了解到，BST的插入是小的往左子树走，大的往右子树走，如果凉心出题人给出的序列是有序的呢这样我们就只能O(N)的操作，GG 旋转(rotate...

数据结构 splay

2019-02-13

0 558

后缀数组详解

##基本概念 ###什么是后缀假如你有一个字符串如 "gzyorz" 它的后缀是 "gzyorz"，"zyorz"，"yorz"，"orz"，"rz"，&q...

字符串数据结构

2019-03-12

0 700

SP375 QTREE - Query on a tree (树剖)

题目 SP375 QTREE - Query on a tree 解析也就是个蓝题，因为比较长树剖裸题（基本上），单点修改，链上查询。顺便来说一下链上操作时如何将边上的操作转化为点上的操作：可以看到这个题然我们对边进行操作，我们的树剖是对节点进行操作的，所以我们考虑把边权变为点权。 ...

树链剖分数据结构

2019-05-04

0 541

P2801 教主的魔法 (线段树)

题目 P2801 教主的魔法解析成天做水题线段树，第一问区间加很简单第二问可以维护一个区间最大值和一个区间最小值，若C小于等于区间最小值，就加上区间长度，若C大于区间最大值，就加0 ps:求教指针线段树，我的空间怎么那么大代码 #include <bits/stdc++.h...

数据结构线段树

2019-06-05

0 522

P2184 贪婪大陆 (树状数组)

题目 P2184 贪婪大陆解析差分？在所修改的区间的开头位置+1，表示从这个位置开始往后开始埋一种地雷，在结尾位置+1，表示在这个位置有一种地雷被埋完查询的时候我们就只需要查询 \([1,r]\)中开头的位置，表示\(1\)到r***埋了多少种类型的地雷 \([1,l-1]...

数据结构差分树状数组

2019-06-01

0 607