对于非2次幂数该如何建树

_8008008 @ 2023-09-06 10:33:42

by Sio_ @ 2023-09-06 10:37:02

都不是

by Azure_Space @ 2023-09-06 10:40:05

都不是吧，线段树每次递归建树都会把数据划分成两个长度相近的区间

by Sio_ @ 2023-09-06 10:41:59

你是要把线段树当01trie树建吗/jk

by Sio_ @ 2023-09-06 10:44:59

但你如果真像01trie一样建也没啥问题，因为线段树能做的01trie都能做

by _8008008 @ 2023-09-06 10:52:27

@youjikai 那是这样吗

by Sio_ @ 2023-09-06 10:59:28

有点小问题，如果你mid=(l+r)/2的话，会直接向下取整，所以如果这样写，你的线段树是右边会大于等于左边节点

by Azure_Space @ 2023-09-06 11:06:58

@Sio_ 就是左边大于等于右边吧

by Sio_ @ 2023-09-06 11:08:39

@youjikai 是的是的/ch，我搞错了

by _XHY20180718_ @ 2023-09-06 12:54:20

@_8008008 正解：动态开点

by _8008008 @ 2023-09-06 14:48:41

已经写出来了(正解)

#include<iostream>
using namespace std;
const int N =100000;
struct node{
    bool cunzai;
    int l,r,sum,lazy;
};
int read(){
    int a;scanf("%d",&a);
    return a;
}
int a[N],n=read(),q=read();node tree[4*N+10]; 
int build(int num,int l,int r){
    tree[num].l=l;tree[num].r=r;
    tree[num].cunzai=true;
    if(l==r){
        tree[num].sum=a[l];
        return tree[num].sum;
    }
    int mid=(l+r)/2;
    tree[num].sum=build(num*2,l,mid)+build(num*2+1,mid+1,r);
    return tree[num].sum;
}
int ans_l,ans_r;
int sum(int num){
    int l=tree[num].l,r=tree[num].r,mid=(l+r)/2,ans=0;
    if(ans_l<=l&&ans_r>=r)return tree[num].sum+tree[num].lazy;
    if(ans_l<=mid){
        if(tree[num].lazy!=0){
            tree[num*2].lazy+=tree[num].lazy;
            tree[num*2+1].lazy+=tree[num].lazy;
            tree[num].sum+=tree[num].lazy;
            tree[num].lazy=0;
        }
        ans+=sum(num*2);
    }
    if(ans_r>=mid+1){
        if(tree[num].lazy!=0){
            tree[num*2].lazy+=tree[num].lazy;
            tree[num*2+1].lazy+=tree[num].lazy;
            tree[num].sum+=tree[num].lazy;
            tree[num].lazy=0;
        }
        ans+=sum(num*2+1);
    }
    return ans;
}
int main(){
    for(int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(q--){
        int moss=read();
        ans_l=read(),ans_r=read();
        if(moss==1){
            int k=read();
            add(1,k);
        }else{
            printf("%d\n",sum(1));
        }
    }
    return 0;
}