线段树1

HYYW1228 · 2024-01-19 07:39:26 · 个人记录

define node {
  info;
  tag;
  void addtag() {}
}

push_down():
  add tag to lson and rson
  update lson and rson
  tag[father] = null

push_up():
  merge lson and rson and assign to tree[father]

update:
  if ql <= l && r <= qr:
     add tag
     update tree[cur]
  push_down()
  leftson and rightson
  push_up()

 query:
   if ql <= l && r<= qr
     return query
   push_down()
   return query of leftson and right son

• 一个节点有tag的时候说明他的值已经被更新过了

• 查询某个节点的时候不需要push up操作因为此次没有进行额外的修改， 所以值在上一次update的时候就被更新过了。所以只需要把tag给左右儿子并更新他们。

• 动态开点是将左右节点的下标替换成了不断增加的id，这样有助于节省空间。

扫描线

• 扫描线每一个节点管理的是一个左闭右开的区间