33DAI：导入1个版本

2026-05-20T18:12:10Z

导入1个版本

←上一版本	2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本	2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:33Z

导入1个版本

←上一版本	2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

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

[https://oj.33dai.cn/p/P3374 【模板】树状数组 1]

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m;
int a[MAXN + 5];
int t[MAXN * 4 + 5];

void build(int now, int l, int r)
{
if (l == r)
{
t[now] = a[l];
return;
}
int mid = (l + r) / 2;
build(now * 2, l, mid);
build(now * 2 + 1, mid + 1, r);
t[now] = t[now * 2] + t[now * 2 + 1];
}

void update(int now, int l, int r, int x, int y)
{
if (l == r)
{
t[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);
t[now] = t[now * 2] + t[now * 2 + 1];
}

int query(int now, int l, int r, int x, int y)
{
if (x <= l && r <= y)
return t[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;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
int op, x, y;
cin >> op;
if (op == 1)
{
cin >> x >> y;
update(1, 1, n, x, y);
}
if (op == 2)
{
cin >> x >> y;
cout << query(1, 1, n, x, y) << "\n";
}
}
return 0;
}
</syntaxhighlight>

== 区间修改、区间查询（懒标记） ==

[https://oj.33dai.cn/p/P3372 【模板】线段树 1]

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n, m;
int a[MAXN + 5];
int t[MAXN * 4 + 5], lazy[MAXN * 4 + 5];

void build(int now, int l, int r)
{
if (l == r)
{
t[now] = a[l];
return;
}
int mid = (l + r) / 2;
build(now * 2, l, mid);
build(now * 2 + 1, mid + 1, r);
t[now] = t[now * 2] + t[now * 2 + 1];
}

void down(int now, int l, int r)
{
int mid = (l + r) / 2;
lazy[now * 2] += lazy[now];
t[now * 2] += (mid - l + 1) * lazy[now];
lazy[now * 2 + 1] += lazy[now];
t[now * 2 + 1] += (r - mid) * lazy[now];
lazy[now] = 0;
}

void update(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
t[now] += (r - l + 1) * z;
lazy[now] += 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)
update(now * 2 + 1, mid + 1, r, x, y, z);
t[now] = t[now * 2] + t[now * 2 + 1];
}

int query(int now, int l, int r, int x, int y)
{
if (x <= l && r <= y)
return t[now];
int mid = (l + r) / 2;
down(now, l, r);
int res = 0;
if (x <= mid)
res += query(now * 2, l, mid, x, y);
if (y > mid)
res += query(now * 2 + 1, mid + 1, r, x, y);
return res;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (m--)
{
int op, x, y, z;
cin >> op;
if (op == 1)
{
cin >> x >> y >> z;
update(1, 1, n, x, y, z);
}
else
{
cin >> x >> y;
cout << query(1, 1, n, x, y) << "\n";
}
}
return 0;
}
</syntaxhighlight>

== 区间加 + 区间乘 + 区间和查询 ==

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 100000;
int n, m, p;
int a[MAXN + 5];
int t[MAXN * 4 + 5];
int lazyAdd[MAXN * 4 + 5], lazyMul[MAXN * 4 + 5];

void build(int now, int l, int r)
{
lazyAdd[now] = 0;
lazyMul[now] = 1;
if (l == r)
{
t[now] = a[l];
return;
}
int mid = (l + r) / 2;
build(now * 2, l, mid);
build(now * 2 + 1, mid + 1, r);
t[now] = (t[now * 2] + t[now * 2 + 1]) % p;
}

void down(int now, int l, int r)
{
int mid = (l + r) / 2;
int add = lazyAdd[now], mul = lazyMul[now];

lazyMul[now * 2] = lazyMul[now * 2] * mul % p;
lazyAdd[now * 2] = (lazyAdd[now * 2] * mul + add) % p;
t[now * 2] = (t[now * 2] * mul + (mid - l + 1) * add) % p;

lazyMul[now * 2 + 1] = lazyMul[now * 2 + 1] * mul % p;
lazyAdd[now * 2 + 1] = (lazyAdd[now * 2 + 1] * mul + add) % p;
t[now * 2 + 1] = (t[now * 2 + 1] * mul + (r - mid) * add) % p;

lazyAdd[now] = 0;
lazyMul[now] = 1;
}

void update_add(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
t[now] = (t[now] + (r - l + 1) * z) % p;
lazyAdd[now] = (lazyAdd[now] + z) % p;
return;
}
int mid = (l + r) / 2;
down(now, l, r);
if (x <= mid)
update_add(now * 2, l, mid, x, y, z);
if (y > mid)
update_add(now * 2 + 1, mid + 1, r, x, y, z);
t[now] = (t[now * 2] + t[now * 2 + 1]) % p;
}

void update_mul(int now, int l, int r, int x, int y, int z)
{
if (x <= l && r <= y)
{
t[now] = t[now] * z % p;
lazyMul[now] = lazyMul[now] * z % p;
lazyAdd[now] = lazyAdd[now] * z % p;
return;
}
int mid = (l + r) / 2;
down(now, l, r);
if (x <= mid)
update_mul(now * 2, l, mid, x, y, z);
if (y > mid)
update_mul(now * 2 + 1, mid + 1, r, x, y, z);
t[now] = (t[now * 2] + t[now * 2 + 1]) % p;
}

int query(int now, int l, int r, int x, int y)
{
if (x <= l && r <= y)
return t[now];
int mid = (l + r) / 2;
down(now, l, r);
int res = 0;
if (x <= mid)
res = (res + query(now * 2, l, mid, x, y)) % p;
if (y > mid)
res = (res + query(now * 2 + 1, mid + 1, r, x, y)) % p;
return res;
}
</syntaxhighlight>

== 动态开点线段树（权值线段树） ==

[https://oj.33dai.cn/p/P1168 中位数]

<syntaxhighlight lang="cpp">
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXAI = 1'000'000'000;
int n, a[MAXN + 5];
int tot = 1;
int lson[MAXN * 30 + 5], rson[MAXN * 30 + 5];
int t[MAXN * 30 + 5];

void update(int now, int l, int r, int x, int y)
{
if (l == r)
{
t[now] += y;
return;
}
int mid = (l + r) / 2;
if (x <= mid)
{
if (!lson[now])
lson[now] = ++tot;
update(lson[now], l, mid, x, y);
}
if (x > mid)
{
if (!rson[now])
rson[now] = ++tot;
update(rson[now], mid + 1, r, x, y);
}
t[now] = t[lson[now]] + t[rson[now]];
}

// 在线段树上二分，找第 k 小
int kth(int now, int l, int r, int k)
{
if (l == r)
return l;
int mid = (l + r) / 2;
if (t[lson[now]] >= k)
return kth(lson[now], l, mid, k);
return kth(rson[now], mid + 1, r, k - t[lson[now]]);
}
</syntaxhighlight>

[[Category:算法模板]]
[[Category:三三文档]]

05-算法模板/02-线段树 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档