高级设计题：跳表与线段树设计

设计跳表（LeetCode 1206）

跳表支持 O(log n) 的查找、插入、删除，是 Redis ZSet 的底层结构之一。

class Skiplist {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    private SkipNode head = new SkipNode(-1, MAX_LEVEL);
    private int level = 1;
    private Random rand = new Random();

    static class SkipNode {
        int val;
        SkipNode[] forward;
        SkipNode(int val, int level) {
            this.val = val;
            forward = new SkipNode[level];
        }
    }

    private int randomLevel() {
        int lv = 1;
        while (rand.nextDouble() < P && lv < MAX_LEVEL) lv++;
        return lv;
    }

    public boolean search(int target) {
        SkipNode cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.forward[i] != null && cur.forward[i].val < target)
                cur = cur.forward[i];
        }
        cur = cur.forward[0];
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        SkipNode[] update = new SkipNode[MAX_LEVEL];
        Arrays.fill(update, head);
        SkipNode cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.forward[i] != null && cur.forward[i].val < num)
                cur = cur.forward[i];
            update[i] = cur;
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) update[i] = head;
            level = newLevel;
        }
        SkipNode newNode = new SkipNode(num, newLevel);
        for (int i = 0; i < newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        SkipNode[] update = new SkipNode[MAX_LEVEL];
        SkipNode cur = head;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.forward[i] != null && cur.forward[i].val < num)
                cur = cur.forward[i];
            update[i] = cur;
        }
        cur = cur.forward[0];
        if (cur == null || cur.val != num) return false;
        for (int i = 0; i < level; i++) {
            if (update[i].forward[i] != cur) break;
            update[i].forward[i] = cur.forward[i];
        }
        while (level > 1 && head.forward[level - 1] == null) level--;
        return true;
    }
}

线段树设计（区间求和、区间更新）

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        build(nums, 0, 0, n - 1);
    }

    private void build(int[] nums, int node, int start, int end) {
        if (start == end) { tree[node] = nums[start]; return; }
        int mid = (start + end) / 2;
        build(nums, 2*node+1, start, mid);
        build(nums, 2*node+2, mid+1, end);
        tree[node] = tree[2*node+1] + tree[2*node+2];
    }

    public void update(int idx, int val, int node, int start, int end) {
        if (start == end) { tree[node] = val; return; }
        int mid = (start + end) / 2;
        if (idx <= mid) update(idx, val, 2*node+1, start, mid);
        else update(idx, val, 2*node+2, mid+1, end);
        tree[node] = tree[2*node+1] + tree[2*node+2];
    }

    public int query(int l, int r, int node, int start, int end) {
        if (r < start || end < l) return 0;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(l, r, 2*node+1, start, mid)
             + query(l, r, 2*node+2, mid+1, end);
    }
}

应用于 LeetCode 307（区域和检索-可变版）。

设计题总结表