线段树+树链剖分专题

此题单适合刚学习线段树的新手到刚学树链剖分的新手

不要脸的宣传文章:线段树 树链剖分

注:在做这些题的时候,有的可能一个代码能过两道题,但请不要这样,试着每次都手打

线段树

1-1 基础线段树

一共3道题,为最简单最基础的线段树题目,不需要任何优化,只要最普通的线段树。

1-2 有懒操作的线段树

一共3道题,如果你试着用最普通的线段树做,你会发现TLE。

这是,就需要一种优化方法——懒操作

1-3 有技巧的线段树

一共4道题。

有些题目,无法使用懒操作,但还会TLE,怎么办呢?

这时候,就需要用一些特别简单的数学常识,用一些小技巧来进行优化~

1-4 线段树进阶

一共3道题。

这里都是线段树的进阶练习,比较难,选做。

树链剖分

1-1树链剖分入门

一共6道题,适合入门者写。

注意一下,如果是树链剖分+线段树的话,一定要给线段树加上懒操作。

1-2 动态开点线段树+树链剖分

一共一道题,比较复杂,主要是线段树部分复杂,要用动态开点线段树

1-3 是边权而不是点权的树链剖分

一共三道题,和上面不同的是,这些并不是点权,而是边权,比较复杂,选做。


  1. P1531 - I Hate It
  2. P1198 - [JSOI2008] 最大数
  3. P1816 - 忠诚
  4. P3372 - 【模板】线段树 1
  5. P3870 - [TJOI2009] 开关
  6. P2574 - XOR的艺术
  7. P4145 - 上帝造题的七分钟 2 / 花神游历各国
  8. CF438D - The Child and Sequence
  9. CF920F - SUM and REPLACE
  10. SP2713 - GSS4 - Can you answer these queries IV
  11. SP1716 - GSS3 - Can you answer these queries III
  12. SP2916 - GSS5 - Can you answer these queries V
  13. SP1557 - GSS2 - Can you answer these queries II
  14. P2982 - [USACO10FEB] Slowing down G
  15. P3384 - 【模板】重链剖分 / 树链剖分
  16. P2590 - [ZJOI2008] 树的统计
  17. P3178 - [HAOI2015] 树上操作
  18. P3833 - [SHOI2012] 魔法树
  19. P2146 - [NOI2015] 软件包管理器
  20. P3313 - [SDOI2014] 旅行
  21. P4114 - Qtree1
  22. P4315 - 月下“毛景树”
  23. P1505 - [国家集训队] 旅游