lrvideckis's blog

2n memory segment tree by choosing midpoint
By lrvideckis, history, 21 month(s) ago, In English

Hi Codeforces! If you calculate midpoint like

int get_midpoint(int l, int r) {//[l, r)
	int pow_2 = 1 << __lg(r-l);//bit_floor(unsigned(r-l));
	return min(l + pow_2, r - pow_2/2);
}

then your segment tree requires only $$$2 \times n$$$ memory.

test
proof

I was inspired by ecnerwala's in_order_layout https://github.com/ecnerwala/cp-book/blob/master/src/seg_tree.hpp

I'll be waiting for some comment "It's well known in china since 2007" 😂

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

»
21 month(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

It's well known in china since 2007

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Thats cool, you're decomposing the segtree into perfect binary trees, not actually caring if the sizes are the same. It gives me some new intuition on the subject.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

maybe you want this Efficient and easy segment trees

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -20 Vote: I do not like it

Segment tree is always 2n memory. I don't get what is new...

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it -14 Vote: I do not like it

    I think recursion makes it nlogn. Edit: why did I get downvoted? I'm probably wrong so can you point out my mistake instead of downvoting?

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Most implementations take 4n memory.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

In fact you can label [l, r] with (l + r | (l != r)), the labels also lay in [2, 2n]

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +67 Vote: I do not like it

You can do this also: let the root be the node $$$0$$$ and let the neighbors for any node $$$x$$$ be $$$x + 1$$$ for the left child, and $$$x + 2(m - l + 1)$$$ for the right child (where $$$[l, r] $$$ is the range which node $$$x$$$ is responsible for, and $$$m$$$ is $$$(l + r) / 2$$$). Also, this is exactly the DFS traversal order of the segment tree.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    That's a really cool trick. It should also slightly improve cache hits when going to the left son (although not by a large amount). This is how tourist's segment tree is implemented, btw.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

This trick is actually pretty cool. I played around with this for a while and got AC a sweepline problem that I got MLE weeks ago. With that said, is there any way, any more tricks that could make this thing faster? Like, I benchmark this method of choosing mid-point, versus the classic method and the latter is around 20% faster, despite consuming twice as much memory (probably because the old method divide the segment into half, making the $$$log$$$ constant per query smaller). Is there any kind of recursive segment tree implementation that is both fast and memory-efficient at the same time?

→ Reply