前缀和 前缀和作用：快速求出元素组中某段区间的和 一维前缀和 原数组: a[1], a[2], a[3], a[4], a[5], …, a[n] 前缀和 S[i] 为数组的前 i 项和 前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i] for循环求出 每个S[i], 将 S[0] 定义为 0，便于处理边界问题 求…
矩阵乘法 二维 乘 二维 void mul(vector<vector<ll>>& c, vector<vector<ll>> a, vector<vector<ll>> b, int p) { int n = a.size(); for (int i = 0; i &…
动态开点线段树原理 例题 1 统计区间中的整数数目 #define ls(x) tr[x].L #define rs(x) tr[x].R class CountIntervals { static const int N = 8e5 + 5; struct node{ int l, r, cnt = 0; int L = -1, R = -1; …
基本数据结构 单链表 // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; } // 在链表头插入一个数a void insert(int a) { e[id…
图的存储 邻接矩阵 int g[N][N]; 链式前向星 // 头插邻接表 N 为点数， M 为点数 int h[N], e[M], w[M], ne[M], idx; void add(int a, int b, int c) { // 插入一条从 a 指向 b 的边，权值为 c e[idx] = b; w[idx] = c; ne[idx] =…