发表于 2025.02.18

• 一开始想到的是前缀和的思路，但由于题目并非是针对某种小数据集的查询（比如小写字母），而是任意数字，因此前缀和会占用大量的空间。因此，我们可以使用哈希表来记录每个数字所出现的位置，然后对于每次查询，使用二分查找来计算区间内的频率：对于查询区间[left, right]，我们先找到第一个大于等于left的位置l，然后找到第一个大于right的位置r，则出现的频率为r - l。

  手动实现二分查找的做法：

  class RangeFreqQuery {
  public:
      RangeFreqQuery(vector<int>& arr) {
          for (int i = 0; i < arr.size(); ++i) occ_map[arr[i]].push_back(i);
      }
      
      int query(int left, int right, int value) {
          if (occ_map.find(value) == occ_map.end()) return 0;
  
          const auto& occ = occ_map[value];
  
          int lo = 0, hi = occ.size() - 1;
          while (lo <= hi) {
              int mid = lo + ((hi - lo) >> 1);
              if (occ[mid] >= left) hi = mid - 1;
              else lo = mid + 1;
          }
          if (lo >= occ.size()) return 0;
          int l = lo;
  
          lo = l, hi = occ.size() - 1;
          while(lo <= hi) {
              int mid = lo + ((hi - lo) >> 1);
              if (occ[mid] > right) hi = mid - 1;
              else lo = mid + 1;
          }
          int r = lo;
  
          return r - l;
      }
  private:
      unordered_map<int, vector<int>> occ_map;
  };

  使用STL算法库的做法：

  class RangeFreqQuery {
  public:
      RangeFreqQuery(vector<int>& arr) {
          for (int i = 0; i < arr.size(); ++i) occ_map[arr[i]].push_back(i);
      }
      
      int query(int left, int right, int value) {
          if (occ_map.find(value) == occ_map.end()) return 0;
          const auto& occ = occ_map[value];
          return std::distance(
              std::lower_bound(occ.begin(), occ.end(), left),
              std::upper_bound(occ.begin(), occ.end(), right)
          );
      }
  private:
      unordered_map<int, vector<int>> occ_map;
  };

• LC 题目链接