|
|
| 第1行： |
第1行： |
| ==单点修改区间查询==
| | #REDIRECT [[05-算法模板/02-线段树]] |
| | | [[Category:三三文档]] |
| <syntaxhighlight lang="cpp" line>
| |
| const int MAXN = 500000;
| |
| struct SegTree
| |
| {
| |
| int sum[MAXN * 4 + 5];
| |
| // 根据子节点算当前节点
| |
| void up(int now)
| |
| {
| |
| sum[now] = sum[now * 2] + sum[now * 2 + 1];
| |
| }
| |
| // 基于 a 数组 build
| |
| void build(int a[], int now, int l, int r)
| |
| {
| |
| if (l == r)
| |
| {
| |
| sum[now] = a[l];
| |
| return;
| |
| }
| |
| int mid = (l + r) / 2;
| |
| build(a, now * 2, l, mid);
| |
| build(a, now * 2 + 1, mid + 1, r);
| |
| up(now);
| |
| }
| |
| // 当前节点是 now，对应区间是 l~r
| |
| // 希望给第 x 个数加上 y
| |
| void update(int now, int l, int r, int x, int y)
| |
| {
| |
| if (l == r)
| |
| {
| |
| sum[now] += y;
| |
| return;
| |
| }
| |
| int mid = (l + r) / 2;
| |
| if (x <= mid)
| |
| update(now * 2, l, mid, x, y);
| |
| if (x > mid)
| |
| update(now * 2 + 1, mid + 1, r, x, y);
| |
| up(now);
| |
| }
| |
| // 当前节点是 now，对应区间是 l~r
| |
| // 返回 x~y 在这个区间内的和
| |
| int query(int now, int l, int r, int x, int y)
| |
| {
| |
| if (x <= l && r <= y)
| |
| return sum[now];
| |
| int mid = (l + r) / 2;
| |
| int res = 0;
| |
| if (x <= mid)
| |
| res += query(now * 2, l, mid, x, y);
| |
| if (y >= mid + 1)
| |
| res += query(now * 2 + 1, mid + 1, r, x, y);
| |
| return res;
| |
| }
| |
| };
| |
| </syntaxhighlight>
| |
| | |
| ==区间修改区间查询==
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| const int MAXN = 100000;
| |
| struct SegTree
| |
| {
| |
| int sum[MAXN * 4 + 5];
| |
| int lazy[MAXN * 4 + 5];
| |
| // 根据子节点算当前节点
| |
| void up(int now)
| |
| {
| |
| sum[now] = sum[now * 2] + sum[now * 2 + 1];
| |
| }
| |
| // 把当前节点的lazy传下去
| |
| void down(int now, int l, int r)
| |
| {
| |
| if (lazy[now] == 0)
| |
| return;
| |
| int mid = (l + r) / 2;
| |
| sum[now * 2] += (mid - l + 1) * lazy[now];
| |
| sum[now * 2 + 1] += (r - mid) * lazy[now];
| |
| lazy[now * 2] += lazy[now];
| |
| lazy[now * 2 + 1] += lazy[now];
| |
| lazy[now] = 0;
| |
| }
| |
| // 基于 a 数组 build
| |
| void build(int now, int l, int r)
| |
| {
| |
| if (l == r)
| |
| {
| |
| sum[now] = a[l];
| |
| return;
| |
| }
| |
| int mid = (l + r) / 2;
| |
| build(now * 2, l, mid);
| |
| build(now * 2 + 1, mid + 1, r);
| |
| up(now);
| |
| }
| |
| // 当前节点是 now，对应区间是 l~r
| |
| // 希望给第 x~y 个数加上 z
| |
| void update(int now, int l, int r, int x, int y, int z)
| |
| {
| |
| if (x <= l && r <= y)
| |
| {
| |
| lazy[now] += z;
| |
| sum[now] += (r - l + 1) * z;
| |
| return;
| |
| }
| |
| int mid = (l + r) / 2;
| |
| down(now, l, r);
| |
| if (x <= mid)
| |
| update(now * 2, l, mid, x, y, z);
| |
| if (y >= mid + 1)
| |
| update(now * 2 + 1, mid + 1, r, x, y, z);
| |
| up(now);
| |
| }
| |
| // 当前节点是 now，对应区间是 l~r
| |
| // 返回 x~y 在这个区间内的和
| |
| int query(int now, int l, int r, int x, int y)
| |
| {
| |
| if (x <= l && r <= y)
| |
| return sum[now];
| |
| int mid = (l + r) / 2;
| |
| int res = 0;
| |
| down(now, l, r);
| |
| if (x <= mid)
| |
| res += query(now * 2, l, mid, x, y);
| |
| if (y >= mid + 1)
| |
| res += query(now * 2 + 1, mid + 1, r, x, y);
| |
| return res;
| |
| }
| |
| };
| |
| </syntaxhighlight>
| |
| | |
| ==动态开点线段树（单点修改区间查询）==
| |
| | |
| <syntaxhighlight lang="cpp" line>
| |
| const int MAXN = 500000;
| |
| struct SegTree
| |
| {
| |
| int root, tot;
| |
| int sum[MAXN * 30 + 5];
| |
| int lc[MAXN * 30 + 5]; // 左子节点
| |
| int rc[MAXN * 30 + 5]; // 右子节点
| |
| // 根据子节点算当前节点
| |
| void up(int now)
| |
| {
| |
| sum[now] = sum[lc[now]] + sum[rc[now]];
| |
| }
| |
| // 当前节点是 now，对应区间是 l~r
| |
| // 希望给第 x 个数加上 y
| |
| void update(int &now, int l, int r, int x, int y)
| |
| {
| |
| if (now == 0)
| |
| now = ++tot;
| |
| if (l == r)
| |
| {
| |
| sum[now] += y;
| |
| return;
| |
| }
| |
| int mid = (l + r) / 2;
| |
| if (x <= mid)
| |
| update(lc[now], l, mid, x, y);
| |
| if (x > mid)
| |
| update(rc[now], mid + 1, r, x, y);
| |
| up(now);
| |
| }
| |
| // 当前节点是 now，对应区间是 l~r
| |
| // 返回 x~y 在这个区间内的和
| |
| int query(int &now, int l, int r, int x, int y)
| |
| {
| |
| if (now == 0)
| |
| now = ++tot;
| |
| if (x <= l && r <= y)
| |
| return sum[now];
| |
| int mid = (l + r) / 2;
| |
| int res = 0;
| |
| if (x <= mid)
| |
| res += query(lc[now], l, mid, x, y);
| |
| if (y >= mid + 1)
| |
| res += query(rc[now], mid + 1, r, x, y);
| |
| return res;
| |
| }
| |
| };
| |
| </syntaxhighlight>
| |
| | |
| 注意空间占用，后面使用时得写 st.root 作为 now
| |
| | |
| * st.query(st.root, 1, 1'000'000'000, 1, a[i] - 1);
| |
| * st.update(st.root, 1, n, a[i], 1);
| |
| | |
| [[分类:代码模板]] | |