adamant's blog

By adamant, 7 years ago, In English

Hi everyone!

tl;dr. If you write the following code:

void dfs_sz(int v = 0) {
    sz[v] = 1;
    for(auto &u: g[v]) {
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[g[v][0]]) {
            swap(u, g[v][0]);
        }
    }
}

void dfs_hld(int v = 0) {
    in[v] = t++;
    for(auto u: g[v]) {
        nxt[u] = (u == g[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}

Then you will have such array that subtree of correspond to segment and the path from to the last vertex in ascending heavy path from (which is ) will be subsegment which gives you the opportunity to process queries on pathes and subtrees simultaneously in the same segment tree.

Inspired by Vladyslav's article and Alex_2oo8's problem Persistent Oak. You can find my solution to this problem here to learn how it can be used to maintain persistent hld over the tree.

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hi, big fan of your blogs!

Could you elaborate a bit on how modifications work? The fact that each node has two positions (in, out) and not both are contained in the path query confuses me on how to handle updates and queries both simultaneously. I'd think we need to make sure modifications change both in(v) and out(v) when modifying v for any reason.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi. and will not change, they just indicate borders of subarray corresponding to subtree of .

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I mean the values for the nodes in_v and out_v in the segment tree.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Oh, you got it incorrectly. Each node occur only in position.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, the out is only a marker. No wonder t doesn't increase when setting out, that was bugging me. All clear now, thank you.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is this a specific version of HLD or a short version?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is short version which also allows you to easily make queries to subtrees.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Does it become the normal hld without queries when we comment the lines that contain in and out? Haven't learnt this data structure yet so I try to have a sense about its implementation. This is the neatest implementation I've ever seen and it made me motivated learning about it.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What do you call normal hld? It's hld only if you don't use out array.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very cool and concise implementation, thank you!

»
7 years ago, # |
  Vote: I like it +54 Vote: I do not like it

This blog is 6 months old, but I've just read it and... WOW WOW WOW WOW, it's so great, WOW WOW (sorry, I just have to do it) WOW WOW WOW!!!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Somehow I also missed this post, and I confirm that this trick is ultimately cool.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I'm kind of surprised that you guys didn't know that trick. There was a problem about 2 years ago (which is a way simpler than a problem mentioned in this post).

      PS: I understand that top coders do not care much about HR, codechef, etc. So it's probably ok.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        They are not surprised by technique called HLD which is well known. They are surprised by the fact how easy can it be made in terms of implementation.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, it makes sense :)

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          Not only, but also the fact that batch updates may be performed over subtrees and arbitrary paths across the tree simultaneously using the single segment tree built across the traversal of the tree.

          For example, now I know how to solve the following problem: given a tree on n vertices and q queries of form 1) add x to all numbers in the subtree 2) add x to all numbers on the path 3) find maximum number in the subtree 4) find maximum number on the path, answer all queries in O((n + q)log2n)

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am confused here. Can someone please explain me how this works?

        Does it require two segment tree or just one to solve problem mentioned by Svyat using above method ? How will you do lazy update to add values in subtree rooted at u? and query for maximum in path?

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is it ok that the code doesn't use property?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sure, I just say that heavy edge is which lead to the largest subtree. Obviously it's better for implementation and time complexity is not worse.

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Maybe we don't really need the array out[], since out[u]=in[u]+sz[u]?