### Jajceslav's blog

By Jajceslav, 3 months ago, translation,

Centroid Decomposition is kinda like Divide & Conquer on arrays (merge sort type divide&connquer) but for trees. Ever thought about it that way? Like HLD is a segment tree but for trees, what do you think? nvm just had a fun thought yesterday, never looked at it from this angle, cool (i attached some imagery)

• +116

 » 3 months ago, # |   +84 There is more to say, but to begin with. When you need to solve problem on a tree, try solving it on array and then extend your methods to trees. You just showed examples of those extensions, which I use when facing tough problem sometimes.
•  » » 3 months ago, # ^ |   0 True! Very common trick to solve tree probems, esp. query related, trees are dope
 » 3 months ago, # |   +43 If I am not wrong then we also have: Fenwick Tree for Arrays = Binary Lifting for Trees
•  » » 3 months ago, # ^ |   +46 binary lifting on trees is more like sparse table on arrays actually, in my opinion
•  » » » 3 months ago, # ^ |   +25 Hmm, that makes more sense
•  » » » 3 months ago, # ^ |   +3 True! i guess you could also do disjoint sparse tables on trees with centroid decomposition if you can calculate LCA in O(1) (sparse table will do)
•  » » » 3 months ago, # ^ |   0 binary lifting on trees is more like binary search when implemented like thishttps://codeforces.com/blog/entry/9901?#comment-177904
 » 3 months ago, # |   +164 BITSET is kinda like BITSET on arrays but for trees
•  » » 3 months ago, # ^ |   +19 wow, it hits hard man
•  » » 3 months ago, # ^ |   +16 such ANIMAL...
 » 3 months ago, # |   +32 Similarly, segment tree is persistent divide and conquer on an array.
•  » » 3 months ago, # ^ |   +69 Similarly, persistent segment tree is persistent persistent divide and conquer on an array.
•  » » » 3 months ago, # ^ |   +9 Similarly, persistent n-dimensional (range sum) segment tree is (persistent divide and conquer on) $^{n-1}$ persistent persistent divide and conquer on an array. SpoilerBonus points if this is done in a purely functional language just to add another level of persistence. More bonus points for a left-catenable/consible implementation.
 » 3 months ago, # |   +56 "Binary Search Tree" is literally "binary search on array, but you store the entire recursion tree". "Segment tree" is literally "divide and conquer, but you store the entire recursion history".I wish people teach these kinds of things in classes. This is the definition of knowledge = connect the dots on information.
 » 3 months ago, # |   0 Koreans called this "divide and conquer on tree", before the word centroid decomposition became popular.