Dynamic-2-SUM

Consider the 2-SUM problem: given an array of n integers (possibly with repetitions), and a target integer t find if there exist two distinct elements x, y in the array such that x + y = t. There are multiple approaches to find a O(n log n) solution to this problem. We would like to implement a dynamic version of this problem. In this version, you do not know the number of elements in advance. The input arrives as a sequence of operations. We start with the empty multiset S. Operations are of three types: 1. Insert(k) : Inserts a number k into S. 2. Delete(k): Deletes an instance of the key k from S. If k is not present, no change is made to the data structure. If k is present multiple times, any one instance is deleted. 3. Query (a, b): Prints the number of target values in the closed interval [a, b] such that there are distinct elements x, y in the multiset with x + y = t. Note that by “distinct” above, we mean two distinct elements of the multiset, which could have the same integer value. E.g. if S = {5, 5, 5}, then then Query (10,15) returns the answer 1, whereas Query(17,20) returns the answer 0.