高精度运算 高精度加法： int main() { scanf("%s%s",&a1,&b1); if(a1[0] == '0' && b1[0] == '0') { cout <&…

数据结构 树状数组，堆 线段树  单点，区间 动态开结点 并查集 加了路径压缩之后不能随便撤销 使用启发式合并复杂度是 O(n log n)，按秩合并是 O(nα(n))。 平衡树 treap 比较好写 splay 比较…

模板 #define lowbit(x) x & -x //1D void add(int x,int t) { while(x <= n) { v[x] += t; x += lowbit(x); } }…

简介 ST表用于区间RMQ问题，它可以做到O(nlogn)预处理，O(1)查询最值。相比线段树，更加有利于静态数据的最值问题。主要是利用倍增的思想。 洛谷：P3865 模板 #include <cstdio>…

问题模型 现在有一个这样的问题：有一个数组a，，现在给你w次修改，q次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和。 这个问题很常见，首先分析下朴素做法的时间复杂度，修改是O(1)的时间…