sgt合并

id: sgt_merge

雨天的尾巴

复杂度:

两颗树合并 nlog(n)nlog(n) ????

使用,用处

  • 对每个点都开个线段树,然后合并信息

cf600E neopcs

子节点与父亲节点的线段树合并

例题

  • 洛谷P4556雨天的尾巴
  • 洛谷P3224永无乡
  • 牛客网NOIP赛前集训营-提高组（第一场）T3 保护
  • NOIP 2016D1T2天天爱跑步
  • CF666E

线段树合并的时间复杂度

参考