123gjweq2's blog

By 123gjweq2, 2 months ago, In English

I was reading this: https://cp-algorithms.com/data_structures/segment_tree.html (segment tree) and I noticed something crazy. The create function is unnecessary. You can just call $$$n$$$ update functions. This could actually save 1-2 minutes of typing. Maybe even 10-20 minutes if the segment tree is especially weird.

Edit: okay, I see how this is not optimal. It looks like this would have a time complexity of $$$O(n \cdot log(n))$$$, while the normal creation method has a time complexity of $$$O(n)$$$.

  • Vote: I like it
  • -32
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The build function takes less than a minute to code, wtf are you on about

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

also the time complexity might be the same but the constant factor for calling update N times will be way larger, since we'll be recursively going through a segment multiple times (with some being returned early)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    doing $$$N$$$ updates takes $$$\mathcal{O}(N\cdot\log{N})$$$, building the tree takes $$$\mathcal{O}(N)$$$

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      I think you might be thinking of a heap. Building a heap (which is technically a list, not a tree) is $$$O(n)$$$, but building a segment tree is definitely $$$O(n\cdot \log(n))$$$.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Building a segment tree is O(n) : There are O(n) nodes, and for each node we do O(1) operations.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -31 Vote: I do not like it

          iirc, each tree has $$$n \cdot \log(n)$$$ nodes, so building a segment tree can't be less than $$$O(n \cdot \log(n))$$$.

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

            The last layer of segment tree has n nodes, the penultimate layer has n/2 nodes and so on : n+n/2+n/4+...+1 ~ 2n. Therefore there are O(n) nodes.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              Rev. 2   Vote: I like it -17 Vote: I do not like it

              But here is where I'm confused. Each layer has $$$n$$$ things it stores, right? And the sequence $$$n, \frac{n}{2}, \frac{n}{4} \cdots 4, 2, 1$$$ has $$$\log_2(n)$$$ elements. So wouldn't that mean $$$n \cdot log_2(n)$$$ nodes?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                Rev. 3   Vote: I like it +5 Vote: I do not like it

                the sequence does have $$$\log_2n$$$ elements, but its sum is bounded by $$$2\cdot n$$$, and it's the sum which gives the number of nodes. The number of terms in the sequence — $$$\log_2{n}$$$ — gives the number of layers in the tree

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                There is another way to calculate it: On the last layer there are $$$n$$$ nodes, and every space between two elements will contribute one node (it appeared as "mid" once), so there are $$$2n-1$$$ nodes in total.

                Also the way qwertylkjhg says is much easier.

                What you are wrong with is that " Each layer has $$$n$$$ things it stores". To be precise, it is the total length of the segments which is $$$n$$$, not the number of segments.

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

                  yes, I see that now. It looks like the first layer has 1 node, second has 2, third 4, etc. That makes sense how it is only O(n) nodes.

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

            Nonsense.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            say you are building a segment tree for $$$n$$$ elements. You need the segment tree to be a perfect binary tree — so you need the number of leaves to be the least $$$2^x \geq n$$$, let's call it $$$N$$$, which is bounded by $$$2\cdot n$$$. Total number of nodes in the segment tree will be twice that (actually $$$2\cdot N - 1$$$ but ok)

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

You should use a build function. This could actually save 0.1s-1s of execution. (However this is nothing compared to your 1-2 minutes)

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

    It could be 10-20 minutes depending on the type of tree. I've seen some really weird segment trees before.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Such as range prefix maximum count query with range addition?

      You will 100% get TL if you attempt to update the segment tree $$$O(n)$$$ times on that one problem.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I am not sure, but this is one of the weird ones I have seen: https://leetcode.com/problems/longest-substring-of-one-repeating-character/description/. It is like dp in a segment tree. I have also seen it in an edu problem once. It just takes a few minutes to code out each function.

        Edit: I just checked it using the update method and it was within the time limit. It also shortened the code by a little bit. But you are right, it was quite a bit slower.

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

          It's more like maintaining the length of the prefix and suffix with same characters and has nothing to do with DP... (and you can find this in the GSS series)

          You are not getting TL in that problem only because TL in this problem is loose.

          Anyway I'm not against the fact that sometimes you can use update functions in place of build functions to save coding time. But mentioning it as "crazy" or "unnecessary" just show how ignorant you are.

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

            ok, well I do appreciate you showing me the differences in time complexities.

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

      It won't if you create a merge function:

      $$$t[v] = \text{merge}(t[2v], t[2v + 1])$$$

      This can be reused in the update function, so coding up the merge function is something seperate from the other functions. The build function is almost always gonna be the same if you do this.

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

        That is actually a very good idea. It looks like it makes every single build and update function only a few lines.