Answer Repeated Range Aggregate Queries on a Static BST

Problem

A fixed binary search tree has been converted once by an in-order traversal into the JSON-portable array sortedValues, which is sorted in nondecreasing order and repeats duplicate node values. Given queries, where each query is [low, high], return one [sum, count] pair per query for all values in that inclusive range. Return [0, 0] for an empty range result. Preprocess the fixed array so repeated queries do not scan all values.

Constraints & Assumptions

• 0 <= len(sortedValues) <= 200,000, and duplicate values appear once per BST node.
• There are at most 200,000 queries.
• Values and range bounds are 32-bit signed integers.
• Use signed 64-bit prefix sums in Java and C++; the stated bounds keep every sum within +/-2^53, so Python integers and JavaScript numbers are exact as well.

Clarifications

• Range endpoints are inclusive and low <= high.
• Duplicates contribute separately to both sum and count.
• The public function receives sortedValues and queries; it does not receive or construct a custom tree-node type.
• Return results in the same order as the queries, and let the caller compute an average as sum / count when count is nonzero.

Examples

sortedValues = [1, 3, 3, 5, 8]
queries = [[3, 5], [6, 7]]
output = [[11, 3], [0, 0]]

Hints

Hint: Exploit the fixed input

Convert the tree's ordered values into a representation that supports prefix aggregates.

Hint: Locate query boundaries

Two binary searches can isolate the inclusive slice for each query.

Answer Repeated Range Aggregate Queries on a Static BST

Hints

1. Precompute prefix sums over the fixed sorted array.
2. Use lower and upper bounds to isolate each inclusive query slice.

Approach

Build a signed 64-bit prefix-sum array over sortedValues once. For each query, lower bound finds the first index whose value is at least low, and upper bound finds the first index whose value is greater than high. Their half-open slice contains exactly the values in the inclusive range, including every duplicate. Subtracting prefix sums gives the slice sum and subtracting indices gives its count. When the indices are equal, both differences are zero, so the required empty result arises naturally.

• Time complexity: O(n + q log n)
• Space complexity: O(n + q) including returned results