Karashi

分类

树链剖分(2) 补题记(5) 题解(13)

/ 注册

TA的专栏 4篇文章 0人订阅

2022杭电多校题解（补题记）

4篇文章 467人学习

全部文章（共2篇）

浅谈 - 树链剖分

浅谈 - 树链剖分前言：其实只是最近练了一些题后，总结一下下树链剖分，其实就是把一棵树拆成多条树链，而两点之间所访问的树链是logn量级，因此给了我们很大的操作空间而一棵树，根据dfn映射到数组上，一条树链就是数组上一段区间。因此我们可以用前缀和、线段树、树状数组等等进行区间操作，区间操作的...

C++ 线段树树链剖分

2022-02-24

1 361

初遇 - 树链剖分

树链剖分前言：树链剖分，久闻大名。从半年前了解到这个知识点，却一直拖到寒假才来学...emm，确实拖了挺久的。小小总结一下，每个父节点都有一个重儿子和若干轻儿子，从一个轻结点出发，一直沿着重儿子延伸下去，就是一条重链。因此，一颗树就被剖分成了若干重链与若干叶子结点。并且，每一条重链的头都是轻结...

C++ 线段树树链剖分

2022-02-22

2 409