题解：P3372 【模板】线段树 1

Poetry_Killer · 2025-12-15 21:40:58 · 题解

题解：P3372 【模板】线段树 1

解析

本体涉及到了线段树的知识，我们先了解一下什么是线段树：线段树是树形数据结构，高效查询与单点和区间更新操作。

解法

我们可以通过以下步骤来进行查找加法：

• 建树：将数组划分为若干区间节点，每个节点存储对应区间的和。
• 懒标记：记录当前节点需要向下传递的加法值。
• 区间更新：递归找到目标区间，更新节点和并标记懒标记。

• 区间查询：递归找到目标区间，返回区间和。

  AC Code

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const int MAXN = 1e5 + 10;
  //4倍空间
  ll sum[4 * MAXN], lazy[4 * MAXN];
  // 原数组
  ll a[MAXN];
  int n, m;
  void pushdown(int node, int l, int r) {
  if (lazy[node] == 0) return; 
  int mid = (l + r) / 2;
  int left = node * 2, right_node = node * 2 + 1;
  // 更新左子节点和
  sum[left] += lazy[node] * (mid - l + 1);
  // 左子节点标记累加
  lazy[left] += lazy[node];
  // 更新右子节点和
  sum[right_node] += lazy[node] * (r - mid);
  // 右子节点标记累加
  lazy[right_node] += lazy[node];
  // 清空当前节点标记
  lazy[node] = 0;
  }
  void build(int node, int l, int r) {
  lazy[node] = 0; 
  if (l == r) {
      sum[node] = a[l];
      return;
  }
  int mid = (l + r) / 2;
  build(node * 2, l, mid);      
  build(node * 2 + 1, mid + 1, r);
  sum[node] = sum[node * 2] + sum[node * 2 + 1]; 
  }
  void update(int node, int l, int r, int ul, int ur, ll k) {
  if (ul <= l && r <= ur) {
      sum[node] += k * (r - l + 1);
      lazy[node] += k;             
      return;
  }
  pushdown(node, l, r); 
  int mid = (l + r) / 2;
  if (ul <= mid) update(node * 2, l, mid, ul, ur, k);
  if (ur > mid) update(node * 2 + 1, mid + 1, r, ul, ur, k);
  sum[node] = sum[node * 2] + sum[node * 2 + 1];
  }
  ll query(int node, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
      return sum[node];
  }
  pushdown(node, l, r); 
  int mid = (l + r) / 2;
  ll res = 0;
  if (ql <= mid) res += query(node * 2, l, mid, ql, qr);
  if (qr > mid) res += query(node * 2 + 1, mid + 1, r, ql, qr);
  return res;
  }
  int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
      cin >> a[i];
  }
  build(1, 1, n); // 根节点编号为1，对应区间[1,n]
  while (m--) {
      int op;
      cin >> op;
      if (op == 1) { // 区间加法操作
          int x, y;
          ll k;
          cin >> x >> y >> k;
          update(1, 1, n, x, y, k);
      } else { // 区间求和操作
          int x, y;
          cin >> x >> y;
          cout << query(1, 1, n, x, y) << '\n';
      }
  }
  
  return 0;
  }

  注意事项：

• 线段树要开 4 倍空间！