改一个值再查一次

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

把下标 2 上的 15 改成 30，然后重新建树、查下标 1 到 3 的和。（这里偷个懒：改完之后整棵树重建一次；真正的线段树只需要沿一条路往上更新，下一节就写。）

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 把求和换成求最大线段树数组要开多大 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

const vector<long long> A5 = {17, 24, 15, 13, 23};

void seg_build(const vector<long long>& a, int node, int l, int r, vector<long long>& tree) {
    if (l == r) {
        tree[node] = a[l];
        return;
    }
    int m = (l + r) / 2;
    seg_build(a, node * 2, l, m, tree);
    seg_build(a, node * 2 + 1, m + 1, r, tree);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long long seg_sum(int node, int l, int r, int ql, int qr, const vector<long long>& tree) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return tree[node];
    int m = (l + r) / 2;
    return seg_sum(node * 2, l, m, ql, qr, tree) + seg_sum(node * 2 + 1, m + 1, r, ql, qr, tree);
}

int main() {
    vector<long long> A = A5;
    // TODO: 把 A[2] 改成 30（要在建树之前改）
    vector<long long> tree(4 * A.size());
    seg_build(A, 1, 0, 4, tree);
    cout << seg_sum(1, 0, 4, 1, 3, tree) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

改一个值再查一次

更多题目

全部评论