Discretization

Introduction

Discretization is a data-processing technique. In essence, it can be viewed as a kind of hashing that preserves the original total/partial order of the data after hashing.

In plain terms, when some data is too large or its type is unsupported, so it cannot conveniently be used as an array index, but only the relative order of the elements affects the final result, we can process the original data according to rank. This is discretization.

Values that can be discretized include large integers, floating-point numbers, strings, and so on.

Implementation

A common application is to discretize an array and then perform queries on it.

Method 1

The original array usually contains duplicate elements, and equal elements are generally discretized to the same value.

The procedure is as follows:

1. Create a copy of the original array.

2. Sort the values in the copy in ascending order.

3. Remove duplicates from the sorted copy.

4. Find the position of each element of the original array in the copy. This position is its rank and becomes its discretized value.

// arr[i] is the initial array, with indices in [1, n]

for (int i = 1; i <= n; ++i)  // step 1
  tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
  arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

The STL algorithms used in the reference implementation are described in STL algorithms.

Similarly, we can discretize a std::vector:

// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp is a copy of arr
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

Method 2

Depending on the problem, equal elements are sometimes discretized to different values according to their order of appearance in the input.

In this case, implementing the procedure with std::lower_bound() is somewhat difficult, so a different approach is needed:

1. Create a copy of the original array and record the position at which each element occurs.

2. Sort the copy by value in ascending order; when values are equal, sort by position in ascending order.

3. Put the discretized values back into the original array.

struct Data {
  int idx, val;

  bool operator<(const Data& o) const {
    if (val == o.val)
      return idx < o.idx;  // when values are equal, the earlier element gets the smaller discretized value
    return val < o.val;
  }
} tmp[MAXN];  // std::pair can also be used

for (int i = 1; i <= n; ++i) tmp[i] = Data{i, arr[i]};
std::sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; ++i) arr[tmp[i].idx] = i;

Complexity

For Method 1, deduplication takes $O(n)$ time, sorting takes $O(n \log n)$ time, and the final $n$ searches take $O(n \log n)$ time.

For Method 2, sorting takes $O(n \log n)$ time.

Therefore, both methods have total time complexity $O(n \log n)$.

The space complexity is $O(n)$.

Exercises

• [HAOI2014] Posting Posters
• [NOI2015] Program Automatic Analysis