高精度运算 高精度加法: int main() { scanf("%s%s",&a1,&b1); if(a1[0] == '0' && b1[0] …
标签:数据结构
#C/C++#数据结构:树状数组/线段树/并查集/树链剖分
数据结构 树状数组,堆 线段树 单点,区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n),按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较…
#C/C++#数据结构:一维树状数组/二维树状数组模板
模板 #define lowbit(x) x & -x //1D void add(int x,int t) { while(x <= n) { v[x] += t; x += lowbit(x); } }…
#C/C++#数据结构:ST表模板
简介 ST表用于区间RMQ问题,它可以做到O(nlogn)预处理,O(1)查询最值。相比线段树,更加有利于静态数据的最值问题。主要是利用倍增的思想。 洛谷:P3865 模板 #include <cstdio>…
#C/C++#树状数组模板
问题模型 现在有一个这样的问题:有一个数组a,,现在给你w次修改,q次查询,修改的话是修改数组中某一个元素的值;查询的话是查询数组中任意一个区间的和。 这个问题很常见,首先分析下朴素做法的时间复杂度,修改是O(1)的时间…