线段树基础求和与修改

胡乱分析

说到线段树实际上还是一个具有叫做lazy tag的完全二叉树

分布操作

建树

建树操作需要知道一个就是当前p的左儿子是2p右儿子是2p+1然后我们递归建树即可，回溯的时候更新每个值
所以代码就比较清晰了，如果当前l=r的话那么我们就把这个叶子节点赋值然后向上回溯即可

void build(int p,int l,int r)
{
  t[p].l=l;t[p].r=r;
  if(l==r)
  {
    t[p].sum=num[l];
    return;
  }
  int mid=(l+r)>>1;
  build(2*p,l,mid);
  build(2*p+1,mid+1,r);
  t[p].sum=t[2*p].sum+t[2*p+1].sum;
}

lazy tag下放

lazy tag在这里是记录区间总共更改了多少，下放的时候要注意更改左右儿子的值并且把左右儿子的lazy tag更新，自己的lazy tag清除

void lazy(int p)
{
  if(t[p].tag)
  {
    t[2*p].sum+=t[p].tag*(t[2*p].r+1-t[2*p].l);
    t[2*p+1].sum+=t[p].tag*(t[2*p+1].r+1-t[2*p+1].l);
    t[2*p].tag+=t[p].tag;
    t[2*p+1].tag+=t[p].tag;
    t[p].tag=0;
  }
}

更改操作

更改是把父节点对应的子节点的个数乘以修改的值，因为每个节点都加上一个数，所以一次把加和给父节点，并且给父节点打上lazy tag,如果修改的区间并不覆盖父节点所管理的范围，那么下放lazy tag并且递归更改其他区间，最后回溯赋值

void change(int p,int x,int y,int z)
{
  if(t[p].l>=x&&t[p].r<=y)
  {
    t[p].sum+=1LL*z*(t[p].r+1-t[p].l);
    t[p].tag+=z;
    return;
  }
  lazy(p);
  int mid=(t[p].r+t[p].l)>>1;
  if(x<=mid)
  change(p*2,x,y,z);
  if(y>mid)
  change(p*2+1,x,y,z);
  t[p].sum=t[2*p].sum+t[2*p+1].sum;
}

查询

查询需要看当前是不是已经区间覆盖了，如果是那么返回当前的区间的值，否则还是下放lazy tag进行递归寻找

long long sum(int p,int x,int y)
{
  if(t[p].l>=x&&t[p].r<=y)
  return t[p].sum;
  lazy(p);
  int mid=(t[p].r+t[p].l)>>1;
  long long ans=0;
  if(x<=mid)
  ans+=sum(2*p,x,y);
  if(y>mid)
  ans+=sum(2*p+1,x,y);
  return ans;
}

完整模板(洛谷P3372 【模板】线段树 1)

#include <bits/stdc++.h>
using namespace std;
struct node
{
  long long l,r,sum,tag;
}t[666666];
long long num[666666];
void build(int p,int l,int r)
{
  t[p].l=l;t[p].r=r;
  if(l==r)
  {
    t[p].sum=num[l];
    return;
  }
  int mid=(l+r)>>1;
  build(2*p,l,mid);
  build(2*p+1,mid+1,r);
  t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
void lazy(int p)
{
  if(t[p].tag)
  {
    t[2*p].sum+=t[p].tag*(t[2*p].r+1-t[2*p].l);
    t[2*p+1].sum+=t[p].tag*(t[2*p+1].r+1-t[2*p+1].l);
    t[2*p].tag+=t[p].tag;
    t[2*p+1].tag+=t[p].tag;
    t[p].tag=0;
  }
}
void change(int p,int x,int y,int z)
{
  if(t[p].l>=x&&t[p].r<=y)
  {
    t[p].sum+=1LL*z*(t[p].r+1-t[p].l);
    t[p].tag+=z;
    return;
  }
  lazy(p);
  int mid=(t[p].r+t[p].l)>>1;
  if(x<=mid)
  change(p*2,x,y,z);
  if(y>mid)
  change(p*2+1,x,y,z);
  t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
long long sum(int p,int x,int y)
{
  if(t[p].l>=x&&t[p].r<=y)
  return t[p].sum;
  lazy(p);
  int mid=(t[p].r+t[p].l)>>1;
  long long ans=0;
  if(x<=mid)
  ans+=sum(2*p,x,y);
  if(y>mid)
  ans+=sum(2*p+1,x,y);
  return ans;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  build(1,1,n);
  while(m--)
  {
    int p,x,y,z;
    cin>>p;
    if(p==1)
    {
      cin>>x>>y>>z;
      change(1,x,y,z);
    }
    else
    {
      cin>>x>>y;
      cout<<sum(1,x,y)<<"\n";
    }
  }
}