Блог пользователя adamant

Автор adamant, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +296
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very cool and concise implementation, thank you!

»
7 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Yeah, it makes sense :)

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +21 Проголосовать: не нравится

          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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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