多项式初步
多项式算法学习笔记定义形如 $\sum a_ix^{i}$ 的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项，定义多项式的次数为项的最高次数。显然 $(n+1)$ 个点可以唯一确定一个次数为 $n$ 的多项式。接下来我们首先来看一下多项式的基本运算怎么实现（要不然谁用啊）多项式加减直接对齐相同次数然后系数直接加减就可以了吧。。。时间复杂度 $O(n)$，难度：普及组 T1（虽然这...
多项式算法学习笔记定义形如 $\sum a_ix^{i}$ 的式子被称为多项式。定义多项式中每个单项式叫做这个多项式的项，定义多项式的次数为项的最高次数。显然 $(n+1)$ 个点可以唯一确定一个次数为 $n$ 的多项式。接下来我们首先来看一下多项式的基本运算怎么实现（要不然谁用啊）多项式加减直接对齐相同次数然后系数直接加减就可以了吧。。。时间复杂度 $O(n)$，难度：普及组 T1（虽然这...
我们把树状数组由一维扩展到二维。二维树状数组的定义是： $C[x][y] = \sum A[i][j]$，其中 $x - lowbit(x) + 1 \leq i \leq x$ $y - lowbit(y) + 1 \leq j \leq y$ 所以我们就可以很方便的写出来单点修改和查询 $(1,1)$ 到 $(x,y)$ 的和的代码了： inline void add(int x,int...
如何维护区间我们都知道平衡树是一种很神奇的东西，可以用于维护动态的序列总信息，但是如果想维护其中的某一个区间的信息，我们该怎么做好呢？我们考虑换一种维护方式：平衡树的结构不是按照节点的值的大小来进行建树，而是以这个节点在序列中的位置为关键字来维护。也就是说对于平衡树中任意一个节点 $x$ ，左子树中的元素永远在它前面，右子树的元素永远在它后面。显然一个区间可以对应一个子树，所以我们要使用能提...
K-D Tree，全名k-dimensional Tree，是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D Tree是二进制空间分割树的特殊的情况，以下是一棵二维空间上的 k-d tree：建树K-D Tree 的建树过程类似于平衡树：对于已知点集，求出其在某一维度上排序后的中间点，作为这个空间的分割点，然后把空间一分为二，再对每个部分...
众所周知 LCT 可以用来维护动态树的点权信息，但是总有一些题目让你维护动态树上的子树信息或者是链信息，就在这里拿一道经典的题目讲一讲。<h2>「UOJ207」共价大爷游长沙</h2>题目链接题目要求维护动态树和一个路径集合，询问某一条边是否被路径集合中所有的路径经过。首先我们考虑一下树是静态的怎么做：显然我们可以yy出一个随机化算法，我们可以对于每一条路径 $(u,...