ITMO Academy pilot course » Segment Tree, part 1 » Step 1 » Practice（ITMO 线段树部分一，第1步的练习，单点修改线段树） · znzryb
## 题目一（普通的单点修改、区间和查询线段树）
**题目描述**
需要编写一个标准的线段树来维护数组的区间和，支持单点修改和区间求和操作。
**输入格式**
第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100000$)，分别表示数组的大小和操作的次数。
第二行包含 $n$ 个整数 $a_i$，表示数组的初始状态 ($0 \le a_i \le 10^9$)。
接下来的行包含操作的描述。每个操作的描述如下：
- `1 i v`：将索引为 $i$ 的元素设置为 $v$ ($0 \le i < n$, $0 \le v \le 10^9$)。
- `2 l r`：计算索引从 $l$ 到 $r-1$ 的元素之和 ($0 \le l < r \le n$)。
**输出格式**
对于每个第二种类型的操作，打印对应的和。
**样例输入**
```
5 5
5 4 2 3 5
2 0 3
1 1 1
2 0 3
1 3 1
2 0 5
```
**样例输出**
```
11
8
14
```
**样例解释**
初始数组为 `[5, 4, 2, 3, 5]`（注意题目中下标从 0 开始）。
1. 操作 `2 0 3`：计算下标 $[0, 3)$ 即 $0, 1, 2$ 的和。$5 + 4 + 2 = 11$。
1. 操作 `1 1 1`：将下标为 1 的元素修改为 1。数组变为 `[5, 1, 2, 3, 5]`。
1. 操作 `2 0 3`：再次计算下标 $[0, 3)$ 的和。$5 + 1 + 2 = 8$。
1. 操作 `1 3 1`：将下标为 3 的元素修改为 1。数组变为 `[5, 1, 2, 1, 5]`。
1. 操作 `2 0 5`：计算下标 $[0, 5)$ 即整个数组的和。$5 + 1 + 2 + 1 + 5 = 14$。
AC
[https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363403398](https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363403398)
::: 源代码
```cpp
/**
* Problem: A. Segment Tree for the Sum
* Contest: ITMO Academy: pilot course
* Judge: Codeforces
* URL: https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A
* Created: 2026-02-17 20:50:46
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct Info {
ll l,r,sum;
friend ostream &operator <<(ostream &os, const Info &a) {
os << "[" << a.l << ";" << a.r << "]";
return os;
}
string to_string() const {
stringstream ss;
ss << *this;
return ss.str();
}
};
Info merge(const Info &a,const Info &b) {
return {a.l,b.r,a.sum+b.sum};
}
struct SEG {
ll N;
vector<Info> infos;
SEG(ll N,const vector<Info> &a) {
infos.resize(4*N+5);
this->N=N;
build(a,1,1,N);
}
void pull(ll u) {
infos[u]=merge(infos[u<<1],infos[u<<1|1]);
}
void build(const vector<Info> &a,ll u,ll l,ll r) {
if (l==r) {
infos[u]=a[l];
infos[u].l=l;
infos[u].r=r;
return;
}
ll mid=l+r>>1;
build(a,u<<1,l,mid);
build(a,u<<1|1,mid+1,r);
pull(u);
}
Info query(ll u,ll l,ll r) {
if (infos[u].l>=l && infos[u].r<=r) {
return infos[u];
}
Info res{};
if (!(infos[u<<1].r<l || infos[u<<1].l>r)) {
res=merge(res,query(u<<1,l,r));
}
if (!(infos[u<<1|1].r<l || infos[u<<1|1].l>r)) {
res=merge(res,query(u<<1|1,l,r) );
}
return res;
}
void assign(ll u,ll pos,const Info &val) {
if (infos[u].l==infos[u].r && infos[u].l==pos) {
infos[u]=val;
infos[u].l=pos;
infos[u].r=pos;
return;
}
if (pos>=infos[u<<1].l && pos<=infos[u<<1].r) {
assign(u<<1,pos,val);
}
if (pos>=infos[u<<1|1].l && pos<=infos[u<<1|1].r) {
assign(u<<1|1,pos,val);
}
pull(u);
}
/*
*AC https://codeforces.com/gym/106169/submission/363483057
*线段树可视化 AC 记录
*/
#ifdef LOCAL
vector<ll> visual_widths;
vector<string> visual_grid;
ll mx_layer = 0;
void visualize() {
visual_widths.resize(4 * N + 2);
cal_visual_w(1, 1);
visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
visualize(1, 0, 1);
for (int i = 1; i <= mx_layer; ++i) {
while (!visual_grid[i].empty() && visual_grid[i].back()==' ') {
visual_grid[i].pop_back();
}
cerr << visual_grid[i] << "\n";
}
}
void cal_visual_w(ll u, ll layer) {
mx_layer = max(mx_layer, layer);
if (infos[u].l == infos[u].r) {
visual_widths[u] = infos[u].to_string().size();
return;
}
cal_visual_w(u << 1, layer + 1);
visual_widths[u] = visual_widths[u << 1] + 3;
cal_visual_w(u << 1 | 1, layer + 1);
visual_widths[u] += visual_widths[u << 1 | 1];
}
// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
if (infos[u].l == infos[u].r) {
string label = infos[u].to_string();
for (ll i = 0; i < label.size(); ++i) {
visual_grid[layer][sc + i] = label[i];
}
return;
}
visualize(u << 1, sc, layer + 1);
string label = infos[u].to_string();
ll pos = label.find(';');
ll labStart = sc + visual_widths[u << 1] + 1 - pos;
for (int i=1;i<=mx_layer;++i) {
if (layer+i>mx_layer) break;
visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
}
// grid[layer + 1][sc + widths[u << 1] + 1] = '|';
// if (layer+2 <= mx_layer) {
// grid[layer+2][sc + widths[u << 1] + 1]='|';
// }
for (ll i = 0; i < label.size(); ++i) {
visual_grid[layer][labStart + i] = label[i];
}
visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
}
#endif
};
void Solve() {
ll N,M;
cin >> N >> M;
vector<Info> A(N+2);
for (int i=1;i<=N;++i) {
cin>>A[i].sum;
}
SEG seg(N,A);
for (int i=1;i<=M;++i) {
ll op;
cin>>op;
if (op==1) {
ll pos,x;
cin>>pos>>x;
pos++;
seg.assign(1,pos,{0,0,x});
}else {
ll l,r;
cin>>l>>r;
l++,r++;
cout<<seg.query(1,l,r-1).sum<<"\n";
}
}
#ifdef LOCAL
seg.visualize();
#endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363403398
*/
```
:::
## 题目 2（单点修改，区间最小值查询线段树）
引入了这个泛型设计。就是假如以后可能有多个 info 的话，可以使用自动模板推导。
AC
[https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363486196](https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363486196)
::: 源代码
```cpp
/**
* Problem: B. Segment Tree for the Minimum
* Contest: ITMO Academy: pilot course
* Judge: Codeforces
* URL: https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/B
* Created: 2026-02-18 16:08:21
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct Info {
// 注意啊，这里这个 MN 记得设一个初值。
ll l, r, mn=INF;
friend ostream &operator <<(ostream &os, const Info &a) {
os << "[" << a.l << ";" << a.r << "]:"<<a.mn;
return os;
}
string to_string() const {
stringstream ss;
ss << *this;
return ss.str();
}
static Info merge(const Info &a, const Info &b) {
return {a.l, b.r, min(a.mn,b.mn)};
}
};
template<class T>
struct SEG {
ll N;
vector<T> infos;
SEG(ll N, const vector<T> &a) {
infos.resize(4 * N + 5);
this->N = N;
build(a, 1, 1, N);
}
void pull(ll u) {
infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
}
void build(const vector<T> &a, ll u, ll l, ll r) {
if (l == r) {
infos[u] = a[l];
infos[u].l = l;
infos[u].r = r;
return;
}
ll mid = l + r >> 1;
build(a, u << 1, l, mid);
build(a, u << 1 | 1, mid + 1, r);
pull(u);
}
T query(ll u, ll l, ll r) {
if (infos[u].l >= l && infos[u].r <= r) {
return infos[u];
}
T res{};
if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
res = T::merge(res, query(u << 1, l, r));
}
if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
res = T::merge(res, query(u << 1 | 1, l, r));
}
return res;
}
void assign(ll u, ll pos, const T &val) {
if (infos[u].l == infos[u].r && infos[u].l == pos) {
infos[u] = val;
infos[u].l = pos;
infos[u].r = pos;
return;
}
if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
assign(u << 1, pos, val);
}
if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
assign(u << 1 | 1, pos, val);
}
pull(u);
}
/*
*AC https://codeforces.com/gym/106169/submission/363483057
*线段树可视化 AC 记录
*/
#ifdef LOCAL
vector<ll> visual_widths;
vector<string> visual_grid;
ll mx_layer = 0;
void visualize() {
visual_widths.resize(4 * N + 2);
cal_visual_w(1, 1);
visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
visualize(1, 0, 1);
for (int i = 1; i <= mx_layer; ++i) {
while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
visual_grid[i].pop_back();
}
cerr << visual_grid[i] << "\n";
}
}
void cal_visual_w(ll u, ll layer) {
mx_layer = max(mx_layer, layer);
if (infos[u].l == infos[u].r) {
visual_widths[u] = infos[u].to_string().size();
return;
}
cal_visual_w(u << 1, layer + 1);
visual_widths[u] = visual_widths[u << 1] + 3;
cal_visual_w(u << 1 | 1, layer + 1);
visual_widths[u] += visual_widths[u << 1 | 1];
}
// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
if (infos[u].l == infos[u].r) {
string label = infos[u].to_string();
for (ll i = 0; i < label.size(); ++i) {
visual_grid[layer][sc + i] = label[i];
}
return;
}
visualize(u << 1, sc, layer + 1);
string label = infos[u].to_string();
ll pos = label.find(';');
ll labStart = sc + visual_widths[u << 1] + 1 - pos;
for (int i = 1; i <= mx_layer; ++i) {
if (layer + i > mx_layer) break;
visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
}
for (ll i = 0; i < label.size(); ++i) {
visual_grid[layer][labStart + i] = label[i];
}
visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
}
#endif
};
void Solve() {
ll N, M;
cin >> N >> M;
vector<Info> A(N + 2);
for (int i = 1; i <= N; ++i) {
cin >> A[i].mn;
}
SEG seg(N, A);
for (int i = 1; i <= M; ++i) {
// #ifdef LOCAL
// seg.visualize();
// #endif
ll op;
cin >> op;
if (op == 1) {
ll pos, x;
cin >> pos >> x;
pos++;
seg.assign(1, pos, {0, 0, x});
} else {
ll l, r;
cin >> l >> r;
l++, r++;
cout << seg.query(1, l, r - 1).mn << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363486196
*/
```
:::
## 题目3（单点修改、区间最小值查询以及区间最小值个数查询线段树）
只需要设计一个新的 merge 函数即可。
```cpp
static Info merge(const Info &a, const Info &b) {
Info res;
res.l=a.l;
res.r=b.r;
res.mn=min(a.mn,b.mn);
if (a.mn==b.mn) {
res.cnt=a.cnt+b.cnt;
}else if (a.mn<b.mn) {
res.cnt=a.cnt;
}else {
res.cnt=b.cnt;
}
return res;
}
```
AC
[https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363488027](https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363488027)
::: 源代码
```cpp
/**
* Problem: C. Number of Minimums on a Segment
* Contest: ITMO Academy: pilot course
* Judge: Codeforces
* URL: https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/C
* Created: 2026-02-18 16:36:09
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
struct Info {
// 注意啊，这里除了 L 和 R 以外的所有你所添加的东西，你都要好好想一想其初值是什么。
ll l=0, r=0, mn=INF,cnt=0;
friend ostream &operator <<(ostream &os, const Info &a) {
os << "[" << a.l << ";" << a.r << "]:"<<"mn:"<<a.mn<<" cnt:"<<a.cnt;
return os;
}
string to_string() const {
stringstream ss;
ss << *this;
return ss.str();
}
static Info merge(const Info &a, const Info &b) {
Info res;
res.l=a.l;
res.r=b.r;
res.mn=min(a.mn,b.mn);
if (a.mn==b.mn) {
res.cnt=a.cnt+b.cnt;
}else if (a.mn<b.mn) {
res.cnt=a.cnt;
}else {
res.cnt=b.cnt;
}
return res;
}
};
template<class T>
struct SEG {
ll N;
vector<T> infos;
SEG(ll N, const vector<T> &a) {
infos.resize(4 * N + 5);
this->N = N;
build(a, 1, 1, N);
}
void pull(ll u) {
infos[u] = T::merge(infos[u << 1], infos[u << 1 | 1]);
}
void build(const vector<T> &a, ll u, ll l, ll r) {
if (l == r) {
infos[u] = a[l];
infos[u].l = l;
infos[u].r = r;
return;
}
ll mid = l + r >> 1;
build(a, u << 1, l, mid);
build(a, u << 1 | 1, mid + 1, r);
pull(u);
}
T query(ll u, ll l, ll r) {
if (infos[u].l >= l && infos[u].r <= r) {
return infos[u];
}
T res{};
if (!(infos[u << 1].r < l || infos[u << 1].l > r)) {
res = T::merge(res, query(u << 1, l, r));
}
if (!(infos[u << 1 | 1].r < l || infos[u << 1 | 1].l > r)) {
res = T::merge(res, query(u << 1 | 1, l, r));
}
return res;
}
void assign(ll u, ll pos, const T &val) {
if (infos[u].l == infos[u].r && infos[u].l == pos) {
infos[u] = val;
infos[u].l = pos;
infos[u].r = pos;
return;
}
if (pos >= infos[u << 1].l && pos <= infos[u << 1].r) {
assign(u << 1, pos, val);
}
if (pos >= infos[u << 1 | 1].l && pos <= infos[u << 1 | 1].r) {
assign(u << 1 | 1, pos, val);
}
pull(u);
}
/*
*AC https://codeforces.com/gym/106169/submission/363483057
*线段树可视化 AC 记录
*/
#ifdef LOCAL
vector<ll> visual_widths;
vector<string> visual_grid;
ll mx_layer = 0;
void visualize() {
visual_widths.resize(4 * N + 2);
cal_visual_w(1, 1);
visual_grid.resize(mx_layer + 2, string(visual_widths[1], ' '));
visualize(1, 0, 1);
for (int i = 1; i <= mx_layer; ++i) {
while (!visual_grid[i].empty() && visual_grid[i].back() == ' ') {
visual_grid[i].pop_back();
}
cerr << visual_grid[i] << "\n";
}
}
void cal_visual_w(ll u, ll layer) {
mx_layer = max(mx_layer, layer);
if (infos[u].l == infos[u].r) {
visual_widths[u] = infos[u].to_string().size();
return;
}
cal_visual_w(u << 1, layer + 1);
visual_widths[u] = visual_widths[u << 1] + 3;
cal_visual_w(u << 1 | 1, layer + 1);
visual_widths[u] += visual_widths[u << 1 | 1];
}
// 可视化线段树
void visualize(ll u, ll sc, ll layer) {
if (infos[u].l == infos[u].r) {
string label = infos[u].to_string();
for (ll i = 0; i < label.size(); ++i) {
visual_grid[layer][sc + i] = label[i];
}
return;
}
visualize(u << 1, sc, layer + 1);
string label = infos[u].to_string();
ll pos = label.find(';');
ll labStart = sc + visual_widths[u << 1] + 1 - pos;
for (int i = 1; i <= mx_layer; ++i) {
if (layer + i > mx_layer) break;
visual_grid[layer + i][sc + visual_widths[u << 1] + 1] = '|';
}
for (ll i = 0; i < label.size(); ++i) {
visual_grid[layer][labStart + i] = label[i];
}
visualize(u << 1 | 1, sc + visual_widths[u << 1] + 3, layer + 1);
}
#endif
};
void Solve() {
ll N, M;
cin >> N >> M;
vector<Info> A(N + 2);
for (int i = 1; i <= N; ++i) {
cin >> A[i].mn;
A[i].cnt=1;
}
SEG seg(N, A);
for (int i = 1; i <= M; ++i) {
// #ifdef LOCAL
// seg.visualize();
// #endif
ll op;
cin >> op;
if (op == 1) {
ll pos, x;
cin >> pos >> x;
pos++;
seg.assign(1, pos, {0, 0, x, 1});
} else {
ll l, r;
cin >> l >> r;
l++, r++;
auto res=seg.query(1, l, r - 1);
cout << res.mn<<" "<<res.cnt << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/submission/363488027
*/
```
:::