线段树空间开4倍的原因

如果证明有错欢迎指出。

对于长为 \(n\) 的序列，显然以其构建的线段树有 \(n\) 个叶子节点

此时线段树的高度为 \(k=\left\lceil{\log_2 n}\right\rceil+1\) （第一层的高度为 \(1\) ）

通过等比数列求和公式 \[ \begin{aligned} S_n= \begin{cases} na_1,&q=1 \\\\ \dfrac{a_1\left(1-q^n\right)}{1-q} = \dfrac{a_1-a_nq}{1-q} ,&q\ne 1 \end{cases} \end{aligned} \] 可知

至多有 \(\dfrac{1\times(1-2^k)}{1-2} = 2^k-1\) 个结点

即有 \(2^{\left\lceil{\log_2 n}\right\rceil+1}-1\) 个结点

根据 \[ \begin{aligned} &\left\lceil{x}\right\rceil- \left\lfloor{x}\right\rfloor=\begin{cases} 0,&\text{if } x \in \mathbb{Z},\\\\ 1,&\text{if }x \notin \mathbb{Z}. \end{cases}\end{aligned} \] 可知

• 当 \(\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;
}