线段树模板 - 版本历史

33DAI：批量导入三三文档

2026-05-20T18:24:18Z

批量导入三三文档

2026年3月8日 (日) 09:01 33DAI

2026-03-08T09:01:03Z

@@ 第130行： / 第130行： @@
 };
 </syntaxhighlight>
 [[分类:代码模板]]

2026年3月8日 (日) 07:49 33DAI

2026-03-08T07:49:03Z

←上一版本		2026年3月8日 (日) 07:49的版本
第57行：		第57行：
	</syntaxhighlight>		</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>

	[[分类:代码模板]]		[[分类:代码模板]]

33DAI：创建页面，内容为“==单点修改区间查询== 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;…”

2026-03-08T06:59:41Z

创建页面，内容为“==单点修改区间查询== <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;…”

新页面

==单点修改区间查询==

<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>

[[分类:代码模板]]

线段树模板 - 版本历史

33DAI：​批量导入三三文档

2026年3月8日 (日) 09:01 33DAI

2026年3月8日 (日) 07:49 33DAI

33DAI：批量导入三三文档