线段树空间开4倍的原因
如果证明有错欢迎指出。
对于长为 $n$ 的序列，显然以其构建的线段树有 $n$ 个叶子节点
此时线段树的高度为 $k=\left\lceil{\log_2 n}\right\rceil+1$ （第一层的高度为 $1$ ）
通过等比数列求和公式
可知
至多有 $\dfrac{1\times(1-2^k)}{1-2} = 2^k-1$ 个结点
即有 $2^{\left\lceil{\log_2 n}\right\rceil+1}-1$ 个结点
根据
可知
当 $\log_2 n$ 为整数时，结点数为 $2n-1$ 个节点
当 $\log_2 n$ 不为整数时，结点数为 $4 \times 2^{\left\lfloor{\log_2 n}\right\rfloor}-1$
$\because \left\lfloor{\log_2 n}\right\rfloor < \log_2 n$
$\therefore 4 \times 2^{\left\lfloor{\log_2 n}\right\rfloor}-1 < 4n-1 < 4n$
很多时候 $n$ 并不恰好为 $2^k$ ，因此开 $4$ 倍空间正好
值得注意的是，对于 ls(at) = at*2 的这种写法
一定要避免在叶子结点调用 ls(at)
因为此时有可能会越界到 $8n$ 的位置
这里贴一个线段树1的代码 卡了点常啥的，无视它（逃
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() readchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
char buf1[SIZ],*p1,*p2;
char readchar()
{
if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
char ch=gc();T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
static T stk[66];T top=0;
do{stk[top++]=k%10,k/=10;}while(k);
while(top){pc(stk[--top]+'0');}
}
#define N (int)(1e5+15)
int n,Q;
int a[N];
struct node
{
int sum,tag;
}t[N<<2];
#define ls(at) (at<<1)
#define rs(at) (at<<1|1)
void push_up(int at)
{
t[at].sum=t[ls(at)].sum+t[rs(at)].sum;
}
void build(int l,int r,int at)
{
if(l==r)
{
t[at].sum=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(at));
build(mid+1,r,rs(at));
push_up(at);
}
void proc(int l,int r,int k,int at)
{
t[at].sum+=k*(r-l+1);
t[at].tag+=k;
}
void push_down(int l,int r,int at)
{
if(t[at].tag)
{
int mid=(l+r)>>1;
proc(l,mid,t[at].tag,ls(at));
proc(mid+1,r,t[at].tag,rs(at));
}
t[at].tag=0;
}
void update(int nl,int nr,int l,int r,int k,int at)
{
if(nl<=l&&r<=nr)
{
t[at].sum+=k*(r-l+1);
t[at].tag+=k;
return;
}
int mid=(l+r)>>1;
push_down(l,r,at);
if(nl<=mid)update(nl,nr,l,mid,k,ls(at));
if(nr>mid)update(nl,nr,mid+1,r,k,rs(at));
push_up(at);
}
int query(int nl,int nr,int l,int r,int at)
{
if(nl<=l&&r<=nr)
{return t[at].sum;}
int mid=(l+r)>>1,res=0;
push_down(l,r,at);
if(nl<=mid)res+=query(nl,nr,l,mid,ls(at));
if(nr>mid)res+=query(nl,nr,mid+1,r,rs(at));
return res;
}
signed main()
{
read(n);read(Q);
for(int i=1; i<=n; i++)
read(a[i]);
build(1,n,1);
while(Q--)
{
int op,l,r,k;
read(op);
if(op==1)
{
read(l);read(r);read(k);
update(l,r,1,n,k,1);
}else
{
read(l);read(r);
write(query(l,r,1,n,1));pc('\n');
}
}
return 0;
}
