Sparse Beacon Sums Problem

Sparse Beacon Sums Problem — ExecCode Hard DSA Practice

Solve the Sparse Beacon Sums problem on ExecCode. Free online hard DSA practice in Searching & Sorting. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Beacons sit on a huge integer line. You only ever add delta at a coordinate (coordinates may repeat; deltas stack). Then you sum every beacon inside [l, r]. A dynamic (sparse) segment tree allocates nodes only where points exist, so the coordinate range can be 1e9. Apply all updates [x, delta] first. Then each query [l, r] is the inclusive sum. You are given: updates — point additions queries — inclusive ranges Return one sum per query. Points outside a query do not contribute. An empty range sum is 0.

Examples

Input {'updates': [[1, 5], [10, 2], [1, 1]], 'queries': [[1, 1], [0, 10], [2, 9]]}; Output [6, 8, 0]. Input {'updates': [[0, 3]], 'queries': [[1, 2]]}; Output [0]. Input {'updates': [[4, -2], [4, 5]], 'queries': [[4, 4]]}; Output [3]

Constraints

Coordinates may be far apart Deltas may be negative

Practice Sparse Beacon Sums free on ExecCode. Browse DSA problems, topic map, and placement guides.