求助：设计支持三种O(lgn)时间复杂度操作的数据结构

Great question! The Decrease(x, y) operation is the tricky one here—updating every element less than x directly would be O(n) in the worst case, which breaks your logarithmic time requirement. The solution lies in using a balanced binary search tree (BST) with lazy propagation (also called lazy updates) to defer bulk changes until they're actually needed.

Core Idea #

We extend a standard balanced BST (like a Red-Black Tree or AVL Tree) with two key additions:

1. A add_delta lazy marker per node, which tracks an increment that needs to be applied to all elements in the node's subtree (but hasn't been propagated to child nodes yet).
2. Per-node subtree_min and subtree_max values, which let us quickly check if an entire subtree's elements are all less than x (so we can apply the bulk update in O(1) time instead of traversing every node).

Node Structure #

Each node will store:

• key: The actual value of the node (adjusted for any applied lazy updates)
• left/right: Pointers to child nodes
• add_delta: The pending increment to apply to all elements in the subtree
• subtree_min: The minimum actual value in the node's subtree
• subtree_max: The maximum actual value in the node's subtree

Key Helper: Lazy Propagation (Push Down) #

Before accessing any node's children, we need to propagate any pending add_delta to ensure child nodes reflect the latest actual values. Here's a simplified implementation sketch:

def push_down(node):
    if node.add_delta == 0:
        return
    # Apply delta to left child if it exists
    if node.left:
        node.left.key += node.add_delta
        node.left.subtree_min += node.add_delta
        node.left.subtree_max += node.add_delta
        node.left.add_delta += node.add_delta
    # Apply delta to right child if it exists
    if node.right:
        node.right.key += node.add_delta
        node.right.subtree_min += node.add_delta
        node.right.subtree_max += node.add_delta
        node.right.add_delta += node.add_delta
    # Clear the delta for current node
    node.add_delta = 0

This operation runs in O(1) time per node, and we only call it when we need to access the node's children.

Operation Breakdown #

1. Insert(x) (O(lgn)) #

This works almost like a standard balanced BST insert, with a few extra steps:

• Traverse the tree to find the correct insertion point, calling push_down on every node along the path to ensure we're working with up-to-date values.
• Create a new node with key = x, add_delta = 0, subtree_min = x, subtree_max = x.
• Insert the node into the tree, then backtrack up the path to update the subtree_min and subtree_max values for all ancestor nodes (since inserting a new element changes the subtree ranges).
• Perform the standard balancing operations (rotations for AVL/Red-Black Trees) to maintain the tree's logarithmic height, updating subtree_min and subtree_max for any nodes affected by rotations.

2. Find(x) (O(lgn)) #

Again, similar to a standard BST search, with lazy propagation:

• Start at the root, call push_down on the current node to ensure its value is up-to-date.
• If node.key == x, return True (element exists).
• If x < node.key, recursively search the left subtree.
• If x > node.key, recursively search the right subtree.
• If you reach a null node, return False.

3. Decrease(x, y) (O(lgn)) #

Remember: Decrease(x, y) means adding y (a negative number) to all elements less than x. Here's how to do it efficiently:

• Start at the root, call push_down to clear any pending updates.
• If the current node is null, return.
• Case 1: Entire subtree is less than x
  If node.subtree_max < x, apply the delta to the entire subtree in O(1) time:
  • Update node.key += y
  • Update node.subtree_min += y
  • Update node.subtree_max += y
  • Add y to node.add_delta (so future accesses to children will inherit this update)
  • Return immediately—no need to traverse children.
• Case 2: No elements in subtree are less than x
  If node.subtree_min >= x, return immediately.
• Case 3: Mixed elements (some < x, some >= x)
  • First, check if the current node's key is less than x—if so, update it directly: node.key += y.
  • Recursively process the left subtree (it may contain elements less than x).
  • If the current node's key is less than x, recursively process the right subtree (since right children could still be less than x).
  • After processing children, update the current node's subtree_min and subtree_max to reflect any changes in its children.

This approach ensures we only traverse O(lgn) nodes—either applying a bulk update to an entire subtree (O(1)) or descending one level in the tree, and the tree's height is logarithmic.

Why This Works #

• Lazy propagation defers bulk updates until they're necessary, avoiding the O(n) cost of updating every element directly.
• The subtree_min and subtree_max values let us quickly skip entire subtrees that don't need updates, keeping the operation logarithmic.
• Insert and Find operations retain their O(lgn) time complexity because we only apply lazy updates along the traversal path, which is length O(lgn).

内容的提问来源于stack exchange，提问作者Ron Dembo