线段树

问题：线段树为什么要开4倍空间

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010;
int q[N];

struct node{
    int l,r;//tree[i].l和tree[i].r分别表示这个点代表的线段的左右下标
    int sum;//tree[i].sum表示这个节点表示的线段和
}tree[N<<2];  //开四倍空间

void pushup(int u){        //更新函数
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum; //父节点的和等于两个子节点之和
}

//一个节点为x 它的父节点为x/2（x>>1） 左儿子2x(x<<1) 右儿子2x+1(x<<1|1)
void build(int u,int l,int r){
    if(l==r){     //左端点等于右端点，即为叶子节点，直接赋值即可
        tree[u].l=l;
        tree[u].r=r;
        tree[u].sum=q[l];
    }
    else{
        tree[u].l=l;
        tree[u].r=r;
        int mid=(l+r)>>1;    //mid则为中间点，左儿子的结点区间为[l,mid],右儿子的结点区间为[m+1,r]
        build(u<<1,l,mid);    //递归构造左儿子结点
        build(u<<1|1,mid+1,r);    //递归构造右儿子结点
        pushup(u);    //更新父节点
    }
}

//区间查询
int query(int u,int l,int r){    //u为结点下标, [l,r]即为要查询的区间
    if(tree[u].l>=l&&tree[u].r<=r)    //如果当前结点的区间包含于(⊆)要查询的区间内，则返回结点信息且不需要往下递归
        return tree[u].sum;

    int sum=0;    //返回值变量，根据具体线段树查询的什么而自定义
    int mid=(tree[u].l+tree[u].r)>>1;    //mid则为中间点，左儿子的结点区间为[l,mid],右儿子的结点区间为[mid+1,r]
    if(l<=mid)   //先找和左边无交集
        sum=query(u<<1,l,r); //左儿子
    if(r>mid)   //再找和右边无交集
        sum+=query(u<<1|1,l,r); //加上右儿子

    return sum;    //返回当前结点得到的信息

}

//单点修改
void modify(int u,int p,int v){    //u为结点下标，p为修改的点，v为要加上的值
    if(tree[u].l==tree[u].r)    //左端点等于右端点，即为叶子结点，直接加上v即可
        tree[u].sum+=v;    //线段树数组都得到修改
    else{
        int mid=(tree[u].l+tree[u].r)>>1;    //mid则为中间点，左儿子的结点区间为[l,mid],右儿子的结点区间为[mid+1,r]
        if(p<=mid)   //如果需要更新的结点在左子树区间
            modify(u<<1,p,v); 
        else if(p>=mid+1)    //如果需要更新的结点在右子树区间
            modify(u<<1|1,p,v);

        pushup(u);    //更新父节点的值
    }
}

int main(){
    int n,m;
    int k,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&q[i]);

    build(1,1,n);

    for(int i=0;i<m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k==0) printf("%d\n",query(1,a,b));
        if(k==1) modify(1,a,b);
    }
    return 0;
}