Which data structure can offer efficient range operation

I think this is a good answer.

LeetCode's 1206 (Design Skiplist) might be "somewhat" similar to what you're hoping to design.

Java

class Skiplist {

    private static final double DEFAULT_PROB = 0.5;
    private final Random rand = new Random();
    private final List<Node> sentinels = new ArrayList<>();

    {
        sentinels.add(new Node(Integer.MIN_VALUE));
    }


    private static final class Node {
        private final int val;
        private Node left, right, up, down;

        private Node(int val) {
            this.val = val;
        }

    }

    public boolean search(int target) {
        Node smallerOrEquals = getSmallerOrEquals(target);
        return smallerOrEquals.val == target;
    }

    public void add(int num) {
        Node curr = getSmallerOrEquals(num);
        final Node nodeToInsert = new Node(num);
        append(curr, nodeToInsert);
        populateLevelUp(nodeToInsert);
    }

    private void populateLevelUp(final Node nodeToInsert) {
        Node curr = nodeToInsert;
        Node currPrev = nodeToInsert.left;

        while (flipCoin()) {
            while (currPrev.left != null && currPrev.up == null)
                currPrev = currPrev.left;

            if (currPrev.up == null) {
                final Node tempSentinel = new Node(Integer.MIN_VALUE);
                currPrev.up = tempSentinel;
                tempSentinel.down = currPrev;
                sentinels.add(currPrev.up);
            }

            currPrev = currPrev.up;
            final Node tempNode = new Node(nodeToInsert.val);
            curr.up = tempNode;
            tempNode.down = curr;
            curr = curr.up;
            currPrev.right = curr;
            curr.left = currPrev;

        }
    }


    private void append(Node prev, Node curr) {
        final Node next = prev.right;
        prev.right = curr;
        curr.left = prev;

        if (next != null) {
            next.left = curr;
            curr.right = next;
        }
    }


    public boolean erase(int num) {
        final Node nodeToRemove = getSmallerOrEquals(num);

        if (nodeToRemove.val != num)
            return false;

        Node curr = nodeToRemove;

        while (curr != null) {
            final Node prev = curr.left;
            final Node next = curr.right;
            prev.right = next;

            if (next != null)
                next.left = prev;

            curr = curr.up;
        }

        return true;
    }

    private Node getSmallerOrEquals(final int target) {
        Node curr = getSentinel();

        while (curr != null) {
            if (curr.right == null || curr.right.val > target) {
                if (curr.down == null)
                    break;

                curr = curr.down;

            } else
                curr = curr.right;

        }

        return curr;
    }

    private boolean flipCoin() {
        return rand.nextDouble() < DEFAULT_PROB;
    }

    private Node getSentinel() {
        return sentinels.get(sentinels.size() - 1);
    }

    public String toString() {
        Node node = sentinels.get(0);
        final StringBuilder sb = new StringBuilder();

        while (node != null) {
            Node iter = node;

            while (iter != null) {
                sb.append(iter.val).append(",");
                iter = iter.up;
            }

            sb.append("\n");
            node = node.right;
        }

        return sb.toString();
    }

}

Python

class Node:
    
    def __init__(self, val, levels):
        self.val = val
        self.levels = [None] * levels


class Skiplist:
    def __init__(self):
        self.head = Node(-1, 16)

    def __iter__(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                future = cur.levels[level]
                if future and future.val < num:
                    cur = future
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self.__iter__(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        node_level = min(16, 1 + int(math.log2(1. / random.random())))
        node = Node(num, node_level)
        for cur, level in self.__iter__(num):
            if level < node_level:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num):
        res = False
        for cur, level in self.__iter__(num):
            future = cur.levels[level]
            if future and future.val == num:
                res = True
                cur.levels[level] = future.levels[level]
        return res

References:

How to implement skiplist?

A skip list can fulfill all these requirements.

• Insert and Remove are already built in for skip list.
• For range(a,b) - you look for the first element smaller/eqauls a, and once found, start iterating the linked list which is the lowest level, until you find b or higher element.