题解 P3372 【【模板】线段树 1】
mcqueen
·
·
题解
注：本文章中 \div 均代表向下取整的整数除法。
线段树的各种操作别的题解已经讲的很多了，我在这里将讲一种特殊的给区间开点的方法。
请看下面一段代码：
inline int ID(int l,int r){return (l+r) | (l!=r);}
这是啥玄学操作。
等等，这种开点方式有什么好的，区间之间的标号难道不会冲突吗？
答：这样开点，你的线段树只要开两倍空间，并且不会冲突。
为什么呢？
证明如下：
令 f(x,y)=x+y 。
考虑一个根节点，它所代表的区间为 [l,r] 。
那它的左儿子代表的区间为 [l,(l+r)\div2] 。
右儿子代表的区间为为 [(l+r)\div2+1,r] 。
我们发现：
这个根节点的右子树的所有节点的 f 值肯定不会等于 f(l,r) ,因为：
当 f(l,r) 为偶数时，右子树中所有节点的最小 f 值为：
**当 $f(l,r)$ 为奇数时**，右子树中所有节点的最小 $f$ 值为：
$(l+r)\div2+1 + (l+r)\div2+1 =l+r+1 ≠ f(l,r) $ 。
------------
同样的，我们讨论左子树：
**当 $f(l,r)$ 为偶数时**，左子树中所有节点的最大 $f$ 值为：
$(l+r)\div2 + (l+r)\div2 = l+r =f(l,r) $ 。
**当 $f(l,r)$ 为奇数时**，左子树中所有节点的最大 $f$ 值为：
$(l+r)\div2 + (l+r)\div2 =l+r-1 ≠ f(l,r) $ 。
综上，只有当 $f(l,r)$ 为偶数时，会与左子树的一个节点（且一定是叶子结点）的 $f$ 值相同。
所以，对于一个非叶子结点：
若 $l+r$ 为偶数，则它的标号为 $l+r+1$ 。
若 $l+r$ 为奇数，则它的标号为 $l+r$ 。
这样就能保证所有的点的标号都不产生冲突了。
又因为任意一个非叶子结点的 $f$ 值一定小于所有它右子树的 $f$ 值。
所以，整棵树中所有点最大的标号为 $n+n=2n$ 。
因此，线段树的空间只要开**两倍**即可。
最后附上本题 AC 代码，各位读者可以结合代码来学会如何运用这样的开点方法：
```cpp
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int n,m;
ll a[N];
struct data
{
ll sum,lazy;
data(){sum=lazy=0;}
}tree[N<<1];
data operator + (const data &x ,const data &y)
{
data ret;
ret.sum=x.sum+y.sum;
return ret;
}
inline int ID(int l,int r){return (l+r) | (l!=r);}
void push_down(int k,int l,int r)
{
int mid=l+r>>1,lson=ID(l,mid),rson=ID(mid+1,r);
ll Lazy=tree[k].lazy;
tree[lson].sum+=Lazy*(mid-l+1);
tree[lson].lazy+=Lazy;
tree[rson].sum+=Lazy*(r-mid);
tree[rson].lazy+=Lazy;
tree[k].lazy=0;
}
void build(int k,int l,int r)
{
if(l==r)
{
tree[k].sum=a[l];
tree[k].lazy=0;
return;
}
int mid=l+r>>1;
int lson=ID(l,mid);
int rson=ID(mid+1,r);
build(lson,l,mid);
build(rson,mid+1,r);
tree[k]=tree[lson]+tree[rson];
}
void update(int k,int l,int r,int L,int R,ll v)
{
if(L<=l&&r<=R)
{
tree[k].lazy+=v;
tree[k].sum+=v*(r-l+1);
return;
}
if(r<L||l>R)return;
int mid=l+r>>1;
push_down(k,l,r);
int lson=ID(l,mid),rson=ID(mid+1,r);
update(lson,l,mid,L,R,v);
update(rson,mid+1,r,L,R,v);
tree[k]=tree[lson]+tree[rson];
}
ll query(int k,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tree[k].sum;
if(r<L||l>R)return 0;
int mid=l+r>>1;
push_down(k,l,r);
int lson=ID(l,mid),rson=ID(mid+1,r);
return query(lson,l,mid,L,R)+query(rson,mid+1,r,L,R);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",a+i);
build(ID(1,n),1,n);//线段树建树函数 build 的调用处传参有误，现已修正。
while(m--)
{
int op,l,r;
ll v;
scanf("%d%d%d",&op,&l,&r);
if(op==1)
{
scanf("%lld",&v);
update(ID(1,n),1,n,l,r,v);
}
else
{
printf("%lld\n",query(ID(1,n),1,n,l,r));
}
}
return 0;
}
```
update 2019.7.27:
在管理员以及巨佬 @alpha1022 的提醒下，将文章的排版更加整齐化。在此感谢他们。
update 2019.7.31:
文章内容中有一处小错误，现已更正。
update 2025.1.22:
线段树建树函数 build 的调用处传参有误，现已修正。优化了文章排版，使其符合现在洛谷题解标准。