79447893

Date: 2025-02-18 10:35:22
Score: 2.5
Natty:
Report link

It's been a long time but the answer doesn't satisfy.

The main reason which in the first place, you have the problem is that the data structure which you drew was wrong.

A range tree need to have the value point at the leaf node not at the branch.

In the picture

The actual graph of your will have to look something like this (taken from: https://www.geeksforgeeks.org/exploring-range-trees/, sorry I am too lazy to draw your case): enter image description here

Here, at each node which isn't the leaf node, the key is the max value of the left subtree. But you can also try another like from this lecture: https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/mit6_046js15_lec09/

As you can see now we can do range query quite easily by finding the split and every leaf from those subtree is in the range.

For more information about the abstract idea of range-tree you can watch the MIT course: https://youtu.be/NMxLL3D5qd8?si=QZH38J44aAZ9hZAH

But a detail implementation is at different course of MIT: https://www.youtube.com/watch?v=TOb1tuEZ2X4.

For 1d only, you can also have an option of using finger search tree to achieve the same time bound.

Reasons:
  • Blacklisted phrase (1): youtu.be
  • Blacklisted phrase (1): youtube.com
  • Long answer (-0.5):
  • No code block (0.5):
  • Low reputation (0.5):
Posted by: KishouYusa