【线段树模板】

线段树模板】"/>

【线段树模板】

这个时候还学线段树让队友知道了估计要喷死我

        以区间查询、修改为名的线段树，学了之后区间查询的题用的挺多，但是修改很多时候只用到了单点修改。例如数组下标作权值，求数组中离当前位置最近的满足条件的数据在哪里，但之前学树剖，自己区间修改照着题解改了好几遍才过，想着要是正赛真要用到区间修改了敲不出100%对的板子就很难受了。

        洛谷线段树模板题P3372

        建树，查询就很简单

void buildTree(int node,int left,int right)
{lazy[node] = 0;if( left == right ){tree[node] = a[left];return ;}int mid = (left+right)/2;buildTree(2*node,left,mid);buildTree(2*node+1,mid+1,right);tree[node] = tree[2*node] + tree[2*node+1];return;
}
long long query(int x,int y,int node,int left,int right)
{// 这里先忽略push_down哈push_down(node,left,right);if( x<=left && right<=y ){return tree[node];}int mid = (left+right)/2;long long ret=0;if( mid>=x )ret += query(x,y,2*node,left,mid);if( mid<y )ret += query(x,y,2*node+1,mid+1,right);return ret;
}

        关键是区间修改怎么写：

        首先，把往下递归到各节点的写出来

void modify(int x,int y,int node,int left,int right,int val)
{if( x<=left && right<=y ){//...}// ...int mid = (left+right)/2;if( mid>=x )modify(x,y,2*node,left,mid,val);if( mid<y )modify(x,y,2*node+1,mid+1,right,val);// ...return ;
}

       假设这么一个线段树：

        现在假设我要修改区间[4,11]的值, 那么这样递归到最后，会有4个modify函数"留"在橙色区间里 :

         这也对应着modify函数里 if( x<=left &&right<=y ){...} 代码段里的内容。这时候，做三件事：

        （1）修改这个节点的值

        （2）将修改的值传给子节点的lazy，因为蓝色标记的节点我们是不会直接修改的，只有在查询查到那个区间时才会更新lazy修改节点

        那么首先写个 push_down函数。该函数用来更新当前节点，并将修改传递给子节点：

inline void push_down(int node,int left,int right)
{if( left > right || lazy[node]==0 )return ;tree[node] += (right-left+1) * lazy[node];lazy[2*node] += lazy[node];lazy[2*node+1] += lazy[node];lazy[node] = 0;return ;
}

        那么 if( x<=left &&right<=y ){...} 里面就是这样：

if( x<=left && right<=y )
{lazy[node] += val;push_down(node,left,right);return ；
}

         那剩下代码，也就是处理modify访问到绿色节点时要做的事情(这里绿色节点我没完全标出)

        首先，既然访问的熬了这个节点，那么这个节点"负责"的区间内的值肯定是要被修改的，但是问题在于只是"部分区间"，如果是区间和可以写成：

int lx = max(left,x), ly = min(right,y);
int tree[node] += val*(ly-lx+1);

        但是这样写不够“泛型”，如果维护的是区间最值，或是区间gcd啥的呢？

        于是考虑等到子节点被修改，后用 tree[node] = tree[2*node] * tree[2*node+1]来修改该节点的值（‘*’指维护的运算，如求和、最值、gcd等）......不过既然要访问获取(子)节点的值，我得先确保访问时其节点的lazy已更新，所以要先push_down子节点。

if( mid>=x )modify(x,y,2*node,left,mid,val);
if( mid<y )modify(x,y,2*node+1,mid+1,right,val);
/** 修改子节点后 */
push_down(2*node,left,mid); push_down(2*node+1,mid+1,right);
tree[node] = tree[2*node] + tree[2*node+1];
return ;

        写这个被旁边的负责数据结构的大佬看到了，不好意思写了

        ->油炸皮卡丘

        然后旁边的旁边的队友最后两分钟A了CF edu场的E题

        我等着星期天上海区域赛被带飞

完整代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include<cstring>
using namespace std;long long a[200010];
long long tree[600010];
long long lazy[600010];
//int Max_node ;inline void push_down(int node,int left,int right)
{if( left > right || lazy[node]==0 )return ;tree[node] += (right-left+1) * lazy[node];lazy[2*node] += lazy[node];lazy[2*node+1] += lazy[node];lazy[node] = 0;return ;
}void buildTree(int node,int left,int right)
{lazy[node] = 0;if( left == right ){tree[node] = a[left];return ;}int mid = (left+right)/2;buildTree(2*node,left,mid);buildTree(2*node+1,mid+1,right);tree[node] = tree[2*node] + tree[2*node+1];return;
}
long long query(int x,int y,int node,int left,int right)
{push_down(node,left,right);if( x<=left && right<=y ){return tree[node];}int mid = (left+right)/2;long long ret=0;if( mid>=x )ret += query(x,y,2*node,left,mid);if( mid<y )ret += query(x,y,2*node+1,mid+1,right);return ret;
}void modify(int x,int y,int node,int left,int right,int val)
{if( x<=left && right<=y ){lazy[node] += val;push_down(node,left,right);return ;}push_down(node,left,right);int mid = (left+right)/2;if( mid>=x )modify(x,y,2*node,left,mid,val);if( mid<y )modify(x,y,2*node+1,mid+1,right,val);push_down(2*node,left,mid); push_down(2*node+1,mid+1,right);tree[node] = tree[2*node] + tree[2*node+1];return ;
}int main()
{int n,m,op;cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",a+i);}buildTree(1,1,n);int x,y,c;for(int t=0;t<m;t++){scanf("%d",&op);if(op==1){scanf("%d %d %d",&x,&y,&c);modify(x,y,1,1,n,c);}else{scanf("%d %d",&x,&y);printf("%lld\n",query(x,y,1,1,n));}}
}