题解：P13825 线段树 1.5

HNO_3 · 2025-08-27 08:28:44 · 题解

动态开点线段树做法

• 这道题与《线段树模板1》的主要区别在于n \le 10^9,但是m \le 10^5,这是本篇题解的主要切入点。

  优点

• 不需要预先分配整个线段树的空间，而是在需要时才创建节点;
• 对于稀疏操作的大规模区间，能节省大量内存;
• 时间复杂度仍保持 O (log n) ;

  数据结构定义

  struct stu
  {
  ll l,r,lazy,sum;
  ll ls,rs;
  }tree[N];

  懒标记下推函数（同时担任build）

  比较特殊的点在于动态创建子节点（判断是否为0，是则未创建）

  void down(ll id)
  {
  stu &a=tree[id];
  if(a.l==a.r) return ;
  ll mid=a.l+(a.r-a.l>>1);
  if(a.ls==0)//无左儿子
  {
      a.ls=++cnt;
      stu &b=tree[cnt];
      b.l=a.l;
      b.r=mid;
      b.sum=init(a.l,mid);
      b.lazy=0;
      b.ls=b.rs=0;
  }
  stu &l=tree[a.ls];
  l.lazy+=a.lazy;
  l.sum+=(l.r-l.l+1)*a.lazy;
  if(a.rs==0)//无右儿子
  {
      a.rs=++cnt;
      stu &b=tree[cnt];
      b.l=mid+1;
      b.r=a.r;
      b.sum=init(mid+1,a.r);
      b.lazy=0;
      b.ls=b.rs=0;
  }
  stu &r=tree[a.rs];
  r.lazy+=a.lazy;
  r.sum+=(r.r-r.l+1)*a.lazy;
  a.lazy=0;
  return ;
  }

• 剩余部分与传统线段树相同;

  时间复杂度分析

• 单次更新和查询操作需要遍历线段树，时间复杂度为 O (log n)
• 整体时间复杂度为 O (m logn)，其中 m 是操作次数

  空间复杂度分析

• 由于使用了动态开点，空间复杂度取决于实际操作涉及的节点数量，最坏情况下为 O (m log n) ;

  最后附上AC代码

• 至于这里 N=10^7+10 是主包试了很久调试出来的，如有更好的方案还请大佬指教;

  #include<bits/stdc++.h>
  #define ll unsigned long long
  using namespace std;
  const int N=1e7+10;
  ll n,m,i,cnt=1;
  struct stu
  {
  ll l,r,lazy,sum;
  ll ls,rs;
  }tree[N];
  ll init(ll l,ll r)
  {
  return (r*(r+1)>>1)-(l*(l-1)>>1);
  }
  void down(ll id)
  {
  stu &a=tree[id];
  if(a.l==a.r) return ;
  ll mid=a.l+(a.r-a.l>>1);
  if(a.ls==0)//无左儿子
  {
      a.ls=++cnt;
      stu &b=tree[cnt];
      b.l=a.l;
      b.r=mid;
      b.sum=init(a.l,mid);
      b.lazy=0;
      b.ls=b.rs=0;
  }
  stu &l=tree[a.ls];
  l.lazy+=a.lazy;
  l.sum+=(l.r-l.l+1)*a.lazy;
  if(a.rs==0)//无右儿子
  {
      a.rs=++cnt;
      stu &b=tree[cnt];
      b.l=mid+1;
      b.r=a.r;
      b.sum=init(mid+1,a.r);
      b.lazy=0;
      b.ls=b.rs=0;
  }
  stu &r=tree[a.rs];
  r.lazy+=a.lazy;
  r.sum+=(r.r-r.l+1)*a.lazy;
  a.lazy=0;
  return ;
  }
  void update(ll id,ll l,ll r,ll v)
  {
  stu &a=tree[id];
  if(a.l>r||a.r<l) return;
  if(a.l>=l&&a.r<=r)
  {
      a.lazy+=v;
      a.sum+=(a.r-a.l+1)*v;
      return ;
  }
  down(id);
  update(a.ls,l,r,v);
  update(a.rs,l,r,v);
  a.sum=tree[a.ls].sum+tree[a.rs].sum;
  }
  ll query(ll id,ll l,ll r)
  {
  if(tree[id].l>r||tree[id].r<l) return 0;
  if(tree[id].l>=l && tree[id].r<=r)
      return tree[id].sum;
  down(id);
  return query(tree[id].ls,l,r)+query(tree[id].rs,l,r);
  }
  int main()
  {
  scanf("%llu%llu",&n,&m);
  stu &a=tree[1];
  a.l=1;a.r=n;
  a.sum=init(1,n);
  a.lazy=0;
  a.ls=a.rs=0;
  while(m--)
  {
      ll q,x,y,z;
      scanf("%llu",&q);
      if(q==1)
      {
          scanf("%llu%llu%llu",&x,&y,&z);
          update(1,x,y,z);
      }
      else
      {
          scanf("%llu%llu",&x,&y);
          printf("%llu\n",query(1,x,y));
      }
  }
  return 0;
  }

  谢谢，还请大佬指教！