Succinct Indexable Dictionary(完備辞書) (structure/wavelet/succinct-indexable-dictionary.hpp)

• View this file on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "structure/wavelet/succinct-indexable-dictionary.hpp"

Required by

• Wavelet Matrix Point Add Rectangle Sum (structure/wavelet/wavelet-matrix-point-add-rectangle-sum.hpp)
• Wavelet Matrix(ウェーブレット行列) (structure/wavelet/wavelet-matrix.hpp)

Verified with

• test/verify/aoj-1549-2.test.cpp
• test/verify/aoj-1549.test.cpp
• test/verify/aoj-2674-2.test.cpp
• test/verify/aoj-2674.test.cpp
• test/verify/yosupo-point-add-rectangle-sum.test.cpp
• test/verify/yosupo-range-kth-smallest-2.test.cpp
• test/verify/yosupo-range-kth-smallest.test.cpp
• test/verify/yosupo-rectangle-sum.test.cpp

Code

/**
 * @brief Succinct Indexable Dictionary(完備辞書)
 */
struct SuccinctIndexableDictionary {
  size_t length;
  size_t blocks;
  vector< unsigned > bit, sum;

  SuccinctIndexableDictionary() = default;

  SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
    bit.assign(blocks, 0U);
    sum.assign(blocks, 0U);
  }

  void set(int k) {
    bit[k >> 5] |= 1U << (k & 31);
  }

  void build() {
    sum[0] = 0U;
    for(int i = 1; i < blocks; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }

  bool operator[](int k) {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }

  int rank(int k) {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }

  int rank(bool val, int k) {
    return (val ? rank(k) : k - rank(k));
  }
};

#line 1 "structure/wavelet/succinct-indexable-dictionary.hpp"
/**
 * @brief Succinct Indexable Dictionary(完備辞書)
 */
struct SuccinctIndexableDictionary {
  size_t length;
  size_t blocks;
  vector< unsigned > bit, sum;

  SuccinctIndexableDictionary() = default;

  SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
    bit.assign(blocks, 0U);
    sum.assign(blocks, 0U);
  }

  void set(int k) {
    bit[k >> 5] |= 1U << (k & 31);
  }

  void build() {
    sum[0] = 0U;
    for(int i = 1; i < blocks; i++) {
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }

  bool operator[](int k) {
    return (bool((bit[k >> 5] >> (k & 31)) & 1));
  }

  int rank(int k) {
    return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
  }

  int rank(bool val, int k) {
    return (val ? rank(k) : k - rank(k));
  }
};

Back to top page