线段树模板：修订间差异

来自三三百科
跳转到导航 跳转到搜索
33DAI​（留言 | 贡献）
行政员、​界面管理员、​管理员
216次编辑
可视化wikitext
33DAI​（留言 | 贡献）
行政员、​界面管理员、​管理员
216次编辑
创建页面，内容为“==单点修改区间查询== <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;…”
 
33DAI​（留言 | 贡献）
行政员、​界面管理员、​管理员
216次编辑
批量导入三三文档
标签：新重定向
 
（未显示同一用户的2个中间版本）
第1行： 第1行：
==单点修改区间查询==
#REDIRECT [[05-算法模板/02-线段树]]
 
[[Category:三三文档]]
<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>
 
 
[[分类:代码模板]]

2026年5月20日 (三) 18:24的最新版本

重定向到：

检索自“https://www.33dai.wiki/index.php?title=线段树模板&oldid=458”