@[Myself_Hisy](/user/922691) 指针玩家,%%%(雾)
目测可能是没有申请空间导致的(本人指针很菜,但是数组的线段树模板还算熟练)
by Wangzj512 @ 2023-10-14 22:21:34
然后就是`addrange`那个右儿子的区间好像没有`|1`
by Wangzj512 @ 2023-10-14 22:23:15
不过这个代码改出来应该是`TLE`(复杂度甚至比数组模拟还多乘一个$O(log_2n)$,悲),实际上区间修改应该还有个叫懒标记的东西。
by Wangzj512 @ 2023-10-14 22:27:26
建议看题解再学一下(线段树的标记还是很有必要学的)。
by Wangzj512 @ 2023-10-14 22:30:28
谢谢大佬
by Kapo_Hisy @ 2023-10-15 08:46:01
嘿嘿嘿,又来求助了……
```cpp
#include<cstdio>
#include<vector>
#define left(key) (key<<1)
#define right(key) (key<<1|1)
#define prev(first,last) (first+last>>1)
#define next(first,last) (first+last>>1|1)
#define int long long
using namespace std;
struct node{
int first,last,sum=0;
};
void build(vector<int> data,int first,int last,int pos,node *tree){
if(first==last){
tree[first].sum=data[first];
tree[first].first=tree[last].last=first;
return;
};
build(data,first,prev(first,last),left(pos),tree);
build(data,next(first,last),last,right(pos),tree);
tree[pos].sum=tree[left(pos)].sum+tree[right(pos)].sum;
};
int query(int first,int last,int pos,node *tree){
if(first==last){
return tree[pos].sum;
};
int lower=tree[pos].first;
int upper=tree[pos].last;
return query(first,prev(lower,upper),left(pos),tree)+query(next(lower,upper),last,right(pos),tree);
};
void range(int add,int first,int last,int pos,node *tree){
if(first==last){
tree[pos].sum+=add;
return;
};
int lower=tree[pos].first;
int upper=tree[pos].last;
range(add,first,prev(lower,upper),left(pos),tree);
range(add,next(lower,upper),last,right(pos),tree);
tree[pos].sum=tree[left(pos)].sum+tree[right(pos)].sum;
};
signed main(signed argc,char **argv){
int maxn,maxm;
scanf("%lld %lld",&maxn,&maxm);
vector<int> data(maxn+1,0);
node *tree=new node[maxn*4+4];
for(int iter=1;iter<=maxn;iter++){
scanf("%lld",&data[iter]);
};
while(maxm--){
int symbol,first,last;
scanf("%lld %lld %lld",&symbol,&first,&last);
if(symbol==1){
int add;
scanf("%lld",&add);
range(add,first,last,1,tree);
}else{
printf("%lld\n",query(first,last,1,tree));
};
};
return 0;
};
```
by Kapo_Hisy @ 2023-10-15 09:11:43
搞错了,没有建树,但是介过也是和指针一样,肯定全RE了……
```cpp
#include<cstdio>
#include<vector>
#define left(key) (key<<1)
#define right(key) (key<<1|1)
#define prev(first,last) (first+last>>1)
#define next(first,last) (first+last>>1|1)
#define int long long
using namespace std;
struct node{
int first,last,sum=0;
};
void build(vector<int> data,int first,int last,int pos,node *tree){
if(first==last){
tree[first].sum=data[first];
tree[first].first=tree[last].last=first;
return;
};
build(data,first,prev(first,last),left(pos),tree);
build(data,next(first,last),last,right(pos),tree);
tree[pos].sum=tree[left(pos)].sum+tree[right(pos)].sum;
};
int query(int first,int last,int pos,node *tree){
if(first==last){
return tree[pos].sum;
};
int lower=tree[pos].first;
int upper=tree[pos].last;
return query(first,prev(lower,upper),left(pos),tree)+query(next(lower,upper),last,right(pos),tree);
};
void range(int add,int first,int last,int pos,node *tree){
if(first==last){
tree[pos].sum+=add;
return;
};
int lower=tree[pos].first;
int upper=tree[pos].last;
range(add,first,prev(lower,upper),left(pos),tree);
range(add,next(lower,upper),last,right(pos),tree);
tree[pos].sum=tree[left(pos)].sum+tree[right(pos)].sum;
};
signed main(signed argc,char **argv){
int maxn,maxm;
scanf("%lld %lld",&maxn,&maxm);
vector<int> data(maxn+1,0);
node *tree=new node[maxn*4+4];
for(int iter=1;iter<=maxn;iter++){
scanf("%lld",&data[iter]);
};
build(data,1,maxn,1,tree);
while(maxm--){
int symbol,first,last;
scanf("%lld %lld %lld",&symbol,&first,&last);
if(symbol==1){
int add;
scanf("%lld",&add);
range(add,first,last,1,tree);
}else{
printf("%lld\n",query(first,last,1,tree));
};
};
return 0;
};
```
by Kapo_Hisy @ 2023-10-15 09:16:17
@[Myself_Hisy](/user/922691) 你的`next`应该是加1不是或1,而且加1要考虑优先级(右移比加1更后计算,所以要给位运算打个括号)
by Wangzj512 @ 2023-10-15 18:42:45
@[Myself_Hisy](/user/922691) 还有,为什么`query`和`range`要往空的一边跑啊(往不需要的地方跑会导致无限递归然后RE)
by Wangzj512 @ 2023-10-15 18:45:28
@[Myself_Hisy](/user/922691) emmm,`build`似乎也没有给全部的`first`和`last`赋值()
by Wangzj512 @ 2023-10-15 18:47:33