Jajceslav's blog

centroid decomposition is kinda divide and conquer but for trees
By Jajceslav, 12 months ago, translation, In English

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)

  • Vote: I like it
  • +116
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +84 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    True! Very common trick to solve tree probems, esp. query related, trees are dope

    → Reply
»
12 months ago, # |
  Vote: I like it +43 Vote: I do not like it

If I am not wrong then we also have: Fenwick Tree for Arrays = Binary Lifting for Trees

→ Reply
»
12 months ago, # |
  Vote: I like it +164 Vote: I do not like it

BITSET is kinda like BITSET on arrays but for trees

→ Reply
»
12 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Similarly, segment tree is persistent divide and conquer on an array.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +69 Vote: I do not like it

    Similarly, persistent segment tree is persistent persistent divide and conquer on an array.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Similarly, persistent n-dimensional (range sum) segment tree is (persistent divide and conquer on) $$$^{n-1}$$$ persistent persistent divide and conquer on an array.

      Spoiler
      → Reply
»
12 months ago, # |
  Vote: I like it +56 Vote: I do not like it

"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.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Koreans called this "divide and conquer on tree", before the word centroid decomposition became popular.

→ Reply