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

View this file on GitHub
View document part on GitHub
Last update: 2026-08-10 15:44:16+00:00
Include: #include "structure/wavelet/succinct-indexable-dictionary.hpp"

ビット列に対して set と rank を高速に処理するデータ構造です。

コンストラクタ

(1) SuccinctIndexableDictionary()
(2) SuccinctIndexableDictionary(size_t length)

(2) は長さ length のビット列を確保します。初期値はすべて 0 です。

制約

$0 \leq length$

計算量

(2) $O(length)$

set

void set(int k)

k 番目のビットを 1 にします。

制約

$0 \leq k < length$

計算量

$O(1)$

build

void build()

rank クエリ用の累積情報を構築します。

set でビットを更新した後は、rank を使う前に build を呼んでください。

計算量

$O(length)$

operator[]

bool operator[](int k)

k 番目のビット値を返します。

制約

$0 \leq k < length$

計算量

$O(1)$

rank

(1) int rank(int k)
(2) int rank(bool val, int k)

(1) 区間 [0, k) に含まれる 1 の個数を返します。
(2) 区間 [0, k) に含まれる val の個数を返します。

制約

$0 \leq k < length$

計算量

$O(1)$

Required by

Verified with

Code

#pragma once

#include <cstddef>
#include <vector>

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

  SuccinctIndexableDictionary() = default;

  SuccinctIndexableDictionary(std::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 2 "structure/wavelet/succinct-indexable-dictionary.hpp"

#include <cstddef>
#include <vector>

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

  SuccinctIndexableDictionary() = default;

  SuccinctIndexableDictionary(std::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)); }
};