kien_coi_1997's blog

By kien_coi_1997, 10 years ago, In English

I discovered a brand new approach to implement insert operator on segment tree.

1. Advantages and disadvantages

There are following advantages:

  • You don't need to know what is tree rotation.
  • Run extremely fast in weak tests / random test cases.

There are following disadvantages:

  • Complexity of each query is O(log^2 max(n)) (amortized)
  • Source code is not shorter than source using balanced tree.

This is example code for impatient people: http://paste.ubuntu.com/8148477/

Because of its complexity, I got TLE in this problem: http://www.spoj.com/problems/QMAX3VN/

Before coding this structure, I thought it will be short, but it is not. However, I want to share with you this structure because I think idea used inside this structure is nice.

2. Properties

  • Size of segment tree is fixed
  • In each node, we maintain two values Max and Count, if u is not leaf, Max[u]=max(Max[u*2], Max[u*2+1), Count[u]=Count[u*2]+Count[u*2+1].
  • Distance between two adjacent is quite long, for example: ----100-----200-----300---- where a - means unused space.
  • The longer distance between two adjacent elements were, the faster queries executed.

3. Insertion

To insert an element valued into k-th position (to be more precise operator insert(k, X) means insert X between (k-1)-th element and k-th element), we find a suitable space to put it in. If we can't find any space, re-arrange a node.

This following example will make you understand.

Firstly, segment tree is empty:

-------------

Insert 1 5: we will insert 100 into middle position:

------5------

Insert 1 6: the most suitable position is 3rd position:

--6---5------

Insert 2 7: choose middle position between element 5 and element 6:

--6-7-5------

Insert 3 8: insert 8 between 7 and 5:

--6-785------

Insert 4 9: we cannot insert 9 between 8 and 5 right now, we must rearrange a node. Let's imagine the tree:

((--6-)(785))((---)(---))

It is impossible to insert 9 between 8 and 5 because node (785) is filled, we will rearrange its parent — node ((--6-)(785)) — as follow:

  • Write its elements into a line: 6, 7, 8, 5
  • Insert 9 between 8 and 5: 6, 7, 8, 9, 5
  • Put elements in suitable places: ------- -> -678-95, if we have more spaces, we will need to rearrange in order to distance between adjacent elements as large as possible, for example: ----------------------------- -> ----6----7----8----9----5----.

4. Accessing k-th element

  • Use value Count in each node to access k-th element in O(log n)

5. Get max of range L..R

  • Execute this query as other segment trees.

6. Prove the complexity

  • In worst cases, each queries run in (log n)^2 amortized.
  • Almost actions work in O(log n), but operator "re-arrange".

In node which have length L, we execute maximal log L operator "re-arrange", the first time occur when number of empty spaces is L/2, the second time is L/4, ...

Complexity to re-arrange a node length L is O(L).

  • There is 1 node length n: O(n log n) * 1
  • There is 2 nodes length n/2: O((n/2) log n) * 2 = O(n log n)
  • There is 4 nodes length n/4: O((n/4) log n) * 4 = O(n log n)
  • ...

In conclusion, complexity to execute n operators insert is O(n (log n)^2)

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

"if we have more spaces, we will need to rearrange in order to distance between adjacent elements as large as possible". You should explain more clearly about this. For example, if our node size is 8 and we have 6 inserted places, how can you distribute them?

You also should consider the case in which we need to insert a new number to the first place 2^k times. I think that your algorithm will be slow on this.

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

    Put x elements into k position:

    • Number of empty position after re-arrangement is k-x.
    • There are x+1 places to put spaces: put b[0] empty elements before first element, b[1] empty elements between 1st element and 2nd element, ..., b[x] empty elements after last element.

    b[] is best when it meets following condition:

    • b[0] + b[1] + .. + b[x] = k-x
    • values of b[0], b[1],.., b[x] is about (k-x)/(x+1)
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This approach reminds me of the Scapegoat Tree...