ITMO Academy pilot course » Segment Tree, part 1 » Step 1 » Practice（ITMO 线段树部分一，第1步的练习，单点修改线段树）

题目一（普通的单点修改、区间和查询线段树）

题目描述

需要编写一个标准的线段树来维护数组的区间和，支持单点修改和区间求和操作。

输入格式

第一行包含两个整数 $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$。

2. 操作 1 1 1：将下标为 1 的元素修改为 1。数组变为 [5, 1, 2, 3, 5]。

3. 操作 2 0 3：再次计算下标 $[0, 3)$ 的和。$5 + 1 + 2 = 8$。

4. 操作 1 3 1：将下标为 3 的元素修改为 1。数组变为 [5, 1, 2, 1, 5]。

5. 操作 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

源代码

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

源代码

/**
 * 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 函数即可。

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

源代码

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

*/