线段树+懒标记

题目分析

本题核心考点为线段树的区间更新（区间加法）与区间查询（区间和）操作。需要实现两种操作：

1. 对区间 $[l, r]$ 内的所有数加上一个值 $v$；
2. 查询区间 $[l, r]$ 内所有数的和。

线段树的优势在于能在 $O(\log n)$ 时间复杂度内完成单次更新/查询，整体复杂度为 $O(n + m\log n)$，可高效处理大数据范围（本题数据范围可到 $n,m \le 4 \times 10^5$）。

算法思路

线段树核心概念

• 懒标记（lazy tag）：延迟更新线段树的子节点，避免重复操作，是区间更新的关键。当需要访问某个节点的子节点时，才将懒标记下传（push_down），保证数据正确性。
• 节点结构：每个节点存储区间左右边界 $[l, r]$、区间和 $sum$、懒标记 $lazy$。

关键操作

1. push_down（下传懒标记）：
   若当前节点有未下传的懒标记，则将标记传递给左右子节点，更新子节点的区间和与懒标记，最后清空当前节点的懒标记。
2. build（建树）：
   递归构建线段树，叶子节点存储原数组值，非叶子节点的区间和为左右子节点之和。
3. update（区间更新）：
   若当前节点区间完全包含在更新区间内，直接更新当前节点的懒标记和区间和；否则下传懒标记，递归更新左右子节点，最后更新当前节点的区间和。
4. query（区间查询）：
   若当前节点区间完全包含在查询区间内，返回当前节点的区间和；否则下传懒标记，递归查询左右子节点并累加结果。

完整代码

#include <bits/stdc++.h>
#define lc k << 1          // 左子节点：k*2
#define rc k << 1 | 1      // 右子节点：k*2+1
#define N 400005           // 原数组最大长度
#define ll long long       // 防止溢出

using namespace std;

// 线段树节点结构
struct node
{
    int l, r;         // 节点管辖的区间 [l, r]
    ll sum, lazy;     // sum：区间和，lazy：懒标记（区间加法）
} tree[N << 2];       // 线段树数组开4倍空间
int n, m;             // n：数组长度，m：操作次数
ll a[N];              // 原数组

// 下传懒标记
void push_down(int k)
{
    if (tree[k].lazy)
    {
        // 更新左子节点
        tree[lc].lazy += tree[k].lazy;
        tree[lc].sum += tree[k].lazy * (tree[lc].r - tree[lc].l + 1);
        // 更新右子节点
        tree[rc].lazy += tree[k].lazy;
        tree[rc].sum += tree[k].lazy * (tree[rc].r - tree[rc].l + 1);
        // 清空当前节点懒标记
        tree[k].lazy = 0;
    }
}

// 建树：k为当前节点编号，l/r为当前区间
void build(int k, int l, int r)
{
    tree[k] = {l, r, 0, 0};
    if (l == r)       // 叶子节点
    {
        tree[k].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1; // 中点
    build(lc, l, mid);      // 建左子树
    build(rc, mid + 1, r);  // 建右子树
    tree[k].sum = tree[lc].sum + tree[rc].sum; // 合并左右子树和
}

// 区间更新：给[l, r]加val，k为当前节点编号
void update(int k, int l, int r, ll val)
{
    if (tree[k].l >= l && tree[k].r <= r) // 当前区间完全在更新区间内
    {
        tree[k].lazy += val;
        tree[k].sum += val * (tree[k].r - tree[k].l + 1);
        return;
    }
    push_down(k); // 下传标记（需要访问子节点）
    int mid = (tree[k].l + tree[k].r) >> 1;
    if (l <= mid) update(lc, l, r, val); // 更新左子树
    if (r > mid)  update(rc, l, r, val); // 更新右子树
    tree[k].sum = tree[lc].sum + tree[rc].sum; // 合并结果
}

// 区间查询：查询[l, r]的和，k为当前节点编号
ll query(int k, int l, int r)
{
    if (tree[k].l >= l && tree[k].r <= r) // 当前区间完全在查询区间内
        return tree[k].sum;
    push_down(k); // 下传标记（需要访问子节点）
    int mid = (tree[k].l + tree[k].r) >> 1;
    ll res = 0;
    if (l <= mid) res += query(lc, l, r); // 查询左子树
    if (r > mid)  res += query(rc, l, r); // 查询右子树
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n); // 建树，根节点编号为1，管辖[1, n]
    while (m--)
    {
        int opt, l, r;
        ll v;
        scanf("%d%d%d", &opt, &l, &r);
        if (opt == 1) // 操作1：区间加
        {
            scanf("%lld", &v);
            update(1, l, r, v);
        }
        else // 操作2：区间查询
            printf("%lld\n", query(1, l, r));
    }
    return 0;
}

代码解释

1. 宏定义

• lc/rc：快速计算左右子节点编号，简化代码；
• N：原数组最大长度，根据题目数据范围设定；
• ll：使用long long防止区间和溢出（本题数据范围下int会溢出）。

2. 节点结构

node结构体存储每个线段树节点的核心信息：

• l/r：节点对应的区间边界；
• sum：区间和；
• lazy：懒标记，记录该区间需要向下传递的加法值。

3. push_down函数

核心作用是延迟更新，只有当需要访问子节点时才下传标记，避免不必要的更新操作，保证效率。

4. build函数

递归构建线段树：

• 叶子节点（l==r）直接赋值为原数组的对应元素；
• 非叶子节点递归构建左右子树，再合并区间和。

5. update函数

处理区间加法：

• 若当前节点区间完全被更新区间包含，直接更新懒标记和区间和；
• 否则下传懒标记，递归更新子节点，最后合并子节点的和。

6. query函数

处理区间和查询：

• 若当前节点区间完全被查询区间包含，直接返回区间和；
• 否则下传懒标记，递归查询子节点并累加结果。

复杂度分析

• 建树：$O(n)$，每个节点仅被访问一次；
• 单次更新/查询：$O(\log n)$，每次递归都会将区间折半；
• 总复杂度：$O(n + m\log n)$，可高效处理$n,m \le 4 \times 10^5$的情况。