CODEWITHSUNDEEP
algorithmdata-structures
xan
xan

Reputation: 1053

Data structure for sequence

I'm training for the test from data structures and I can't solve this problem:

Design a data structure which keeps sequence a_1, ..., a_n and can perform two operations on it:

  1. set a_i to value x
  2. count how many times value x occurs in a sequence between two indexes: i, and j; just to be sure I made it clear (I'm not good at English) it means to return |{a_k: a_k = x and i <= k <= j}| for a given: x, i, j.

constraints:

  • a_i are from interval [0, ..., 10^9],
  • n is smaller - it is less than 10^5

both operations should work in at most O(log n) time. The only way I see it is, unfortunately, O(log^2 n). We keep interval tree with maps<int,int> in nodes, which count how many times x occurs in a subtree. It is also important not to keep in maps values that occur 0 times (memory complexity).

How can I solve it better? Can anyone help?

Upvotes: 2

Views: 269

Answers (1)

Konsol Labapen
Konsol Labapen

Reputation: 2434

This is a BST with two data fields:

BSTNode<E>{
   int index;
   E value;
   BSTNode left, right;
}

Order your tree by the indices so that searching is O(lg n): which helps with inserting and setting (seta_i to value x).

To count how many times value x occurs in a sequence between two indexes: i, j

EDIT:

after finding the common parent of i and j, instead of traversing the subtree, it is possible to simply look up the frequency of a value: Each node (here the commonParent) can have a frequency map: Map<E,Integer> childrenFreq = new HashMap<E,Integer>(). This would be O(1) once the common parent is found in O(lg n)

Upvotes: 6

Related Questions