树状数组

时间复杂度：O(logn)，查询和修改都是
解决问题：单点修改、区间查询，也可以区间修改，单点查询
原理：数组下标必须从 1 开始，如果下标二进制最右边有 k 个 0，那就是第 k 层，lowbit(x) = 2 ^ k，每个 c[x] 存储的是 [x - lowbit(x), x] 区间的和

1.动态求连续区间和

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int c[N];
int n, m;int lowbit(int x){return x & -x;
}void add(int a, int b){for(int i = a; i <= n; i += lowbit(i)) c[i] += b;
}int sum(int x){int res = 0;for(int i = x; i > 0; i -= lowbit(i)) res += c[i];return res;
}int main(){scanf("%d%d", &n, &m);int x;for(int i = 1; i <= n; i++){scanf("%d", &x);add(i, x);}int k, a, b;while(m--){cin>>k>>a>>b;if(k == 1){add(a, b);}else{int res = sum(b) - sum(a - 1);printf("%d\n", res);}}return 0;
}

2.数星星

因为 y 坐标按照增序给出，所以只需要处理 x 坐标

#include<iostream>
using namespace std;
const int N = 4e4 + 10;
int c[N], cnt[N];
int n;int lowbit(int x){return x & -x;
}void add(int a, int b){for(int i = a; i <= N; i += lowbit(i)) c[i] += b;
}int sum(int x){int res = 0;for(int i = x; i > 0; i -= lowbit(i)) res += c[i];return res;
}int main(){scanf("%d", &n);int x, y;for(int i = 1; i <= n; i++){scanf("%d%d", &x, &y);// 下标从 1 开始x++;// 更新左下角星星数目cnt[sum(x)]++;// 更新这个位置的星星数目add(x, 1);}for(int i = 0; i < n; i++) printf("%d\n", cnt[i]);return 0;
}

3.小朋友排队

每一次操作最多只会使逆序对数量减一，交换次数至少是 k（逆序对数量），每位数字左边比他大的数有 k1，右边比他小的数有 k2，他的不高兴之和就是 1 + 2 + … + k1 + k2，所有小朋友加起来就是 2 * k
用树状数组查询大于 ai 和小于 ai 的有多少个，用身高作为下标

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int h[N], c[N], sum[N];
int n;int lowbit(int x){return x & -x;
}void add(int a, int b){for(int i = a; i < N; i += lowbit(i)) c[i] += b;
}int query(int x){int res = 0;for(int i = x; i > 0; i -= lowbit(i)) res += c[i];return res;
}int main(){scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &h[i]);h[i]++;}// 求前面有多少个比他大，顺序遍历for(int i = 0; i < n; i++){sum[i] = query(N - 1) - query(h[i]);add(h[i], 1);}// 求后面有多少个比他小，倒序遍历，记得清空树状数组memset(c, 0, sizeof(c));for(int i = n - 1; i >= 0; i--){sum[i] += query(h[i] - 1);add(h[i], 1);}long long res = 0;for(int i = 0; i < n; i++) res += 1ll * (1 + sum[i]) * sum[i] / 2;printf("%lld", res);return 0;
}

线段树

时间复杂度：O(logn)
解决问题：单点修改，区间查询，区间修改（要懒标记）
操作：1.pushup: 用子节点信息更新当前节点信息，2.build: 在一段区间上初始化线段树，3.modify: 修改，4.query: 查询
最多 4 * n 个点
x 的父节点: x / 2（x >> 1）
左儿子 2 * x（x << 1）
右儿子 2 * x + 1（x << 1 | 1）

1.动态求连续区间和

维护区间和

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int w[N];
int n, m;
struct Node{int l, r;// 维护区间和int sum;
}tr[4 * N];// 把信息往上传递
void pushup(int x){tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
}// 根节点，区间左端点，区间右端点
void build(int x, int l, int r){// 是叶子节点就返回if(l == r) tr[x] = {l, r, w[r]};else{// 不是叶子节点就裂开tr[x] = {l, r};int mid = (l + r) / 2;build(x << 1, l, mid);build(x << 1 | 1, mid + 1, r);pushup(x);}
}int query(int x, int l, int r){if(tr[x].l >= l && tr[x].r <= r) return tr[x].sum;else{int mid = (tr[x].l + tr[x].r) / 2;int sum = 0;if(l <= mid) sum = query(x << 1, l, r);if(r > mid) sum += query(x << 1 | 1, l, r);return sum;}
}// 根节点，插入位置，插入值
void modify(int x, int a, int b){if(tr[x].l == tr[x].r) tr[x].sum += b;else{int mid = (tr[x].l + tr[x].r) / 2;if(a <= mid) modify(x << 1, a, b);else modify(x << 1 | 1, a, b);pushup(x);}
}int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &w[i]);build(1, 1, n);int k, a, b;while(m--){scanf("%d%d%d", &k, &a, &b);if(k == 0) printf("%d\n", query(1, a, b));else modify(1, a, b);}return 0;
}

2.数列区间最大值

维护区间最大值

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int w[N];
int n, m;
struct Node{int l, r;// 维护区间最大值int sum;
}tr[4 * N];void pushup(int x){tr[x].sum = max(tr[x << 1].sum, tr[x << 1 | 1].sum);
}void build(int x, int l, int r){if(l == r) tr[x] = {l, r, w[r]};else{tr[x] = {l, r};int mid = (l + r) / 2;build(x << 1, l, mid);build(x << 1 | 1, mid + 1, r);pushup(x);}
}int query(int x, int l, int r){if(tr[x].l >= l && tr[x].r <= r) return tr[x].sum;else{int mid = (tr[x].l + tr[x].r) / 2;int res = INT32_MIN;// 判断递归到哪个儿子if(l <= mid) res = query(x << 1, l, r);if(r > mid) res = max(res, query(x << 1 | 1, l, r));return res;}
}void modify(int x, int a, int b){if(tr[x].l == tr[x].r) tr[x].sum += b;else{int mid = (tr[x].l + tr[x].r) / 2;if(a <= mid) modify(x << 1, a, b);else modify(x << 1 | 1, a, b);pushup(x);}
}int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &w[i]);build(1, 1, n);int a, b;while(m--){scanf("%d%d", &a, &b);printf("%d\n", query(1, a, b));}return 0;
}

3.油漆面积

扫描线法：还可以是斜着矩阵、三角形、圆形
非常特殊的线段树，延迟更新，不考虑父节点的信息，只考虑子节点的信息
懒标记可以不往下传，所以非常特殊
成对，先加后减，cnt >= 0，只查询根节点

这个线段树是竖着的区间

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10;
int n;
struct Node1{int l, r;// 存储当前区间被覆盖的次数int cnt;// 存储当前区间的长度，竖着的区间int len;
}tr[4 * N];struct Node2{int x, y1, y2;// 存储 1 或 -1，表示成对出现的区间int k;// 根据 x 排序bool operator<(const Node2 &t)const{return x < t.x;}
}seg[2 * N];// 往上更新根节点
void pushup(int x){// 如果被覆盖过，那就更新长度，这个要放在前面if(tr[x].cnt > 0) tr[x].len = tr[x].r - tr[x].l + 1;// 此时为一条线else if(tr[x].l == tr[x].r) tr[x].len = 0;// 否则递归处理else tr[x].len = tr[x << 1].len + tr[x << 1 | 1].len;
}void build(int x, int l, int r){if(l == r) tr[x] = {l, r};else{tr[x] = {l, r};int mid = (l + r) / 2;build(x << 1, l, mid);build(x << 1 | 1, mid + 1, r);}
}void modify(int x, int l, int r, int k){if(tr[x].l >= l && tr[x].r <= r){// 更新被覆盖的次数tr[x].cnt += k;// 传递给根节点pushup(x);}else{int mid = (tr[x].l + tr[x].r) / 2;if(l <= mid) modify(x << 1, l, r, k);if(r > mid) modify(x << 1 | 1, l, r, k);pushup(x);}
}int main(){scanf("%d", &n);int x1, y1, x2, y2, m = 0;for(int i = 0; i < n; i++){scanf("%d%d%d%d", &x1, &y1, &x2, &y2);seg[m++] = {x1, y1, y2, 1};seg[m++] = {x2, y1, y2, -1};}sort(seg, seg + m);build(1, 0, 10000);int res = 0;for(int i = 0; i < m; i++){// 每次都会更新根节点的长度，tr[1].len 就是竖着的区间长度if(i) res += tr[1].len * (seg[i].x - seg[i - 1].x);modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k);}printf("%d", res);return 0;
}