|
|
| （未显示同一用户的1个中间版本） |
| 第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>
| |
| | |
| [[分类:代码模板]] | |