都不是
by Sio_ @ 2023-09-06 10:37:02
都不是吧，线段树每次递归建树都会把数据划分成两个长度相近的区间
by Azure_Space @ 2023-09-06 10:40:05
你是要把线段树当01trie树建吗/jk
by Sio_ @ 2023-09-06 10:41:59
但你如果真像01trie一样建也没啥问题，因为线段树能做的01trie都能做
by Sio_ @ 2023-09-06 10:44:59
@[youjikai](/user/712794) 那是这样吗
by _8008008 @ 2023-09-06 10:52:27
有点小问题，如果你mid=(l+r)/2的话，会直接向下取整，所以如果这样写，你的线段树是右边会大于等于左边节点
by Sio_ @ 2023-09-06 10:59:28
@[Sio_](/user/678673) 就是左边大于等于右边吧
by Azure_Space @ 2023-09-06 11:06:58
@[youjikai](/user/712794) 是的是的/ch，我搞错了
by Sio_ @ 2023-09-06 11:08:39
@[_8008008](/user/803885) 正解：动态开点
by XHY20180718 @ 2023-09-06 12:54:20
~~已经写出来了(正解)~~
```
#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;
}
```
by _8008008 @ 2023-09-06 14:48:41