求助动态开店线段树
  • 板块学术版
  • 楼主yukimianyan
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/2/5 11:18
  • 上次更新2023/10/28 09:40:26
查看原帖
求助动态开店线段树
509229
yukimianyan楼主2022/2/5 11:18

完整代码

void add(T k,int &p,int l,int r){
	if(!p) p=newnode();//这一行是否需要
    ans[p].add(k,l,r),tag[p]+=k;
}
void pushdown(int &p,int l,int r){
        if(tag[p].empty()) return ;
        int mid=(l+r)>>1;
        add(tag[p],ch[p][0],l,mid);
        add(tag[p],ch[p][1],mid+1,r);
        tag[p]=T();
    }

疑问:动态开店线段树中,如果要下传懒标记却发现子节点不存在时:

  1. 是否需要新建这个子节点?
  2. 如果需要,则这颗线段树修改一次所花费的最大空间是多少?
  3. 如果不需要,则应如何处理这个懒标记?

谢谢

2022/2/5 11:18
加载中...