Succinct-Indexable-Dictionary
(structure/wavelet/succinct-indexable-dictionary.hpp)

• View this file on GitHub
• Last update: 2024-10-04 14:05:18+02:00
• Include: #include "structure/wavelet/succinct-indexable-dictionary.hpp"

Code

/*
 * @brief Succinct-Indexable-Dictionary
 * @docs docs/succinct-indexable-dictionary.md
 */

#include <bits/stdc++.h>
using namespace std;

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
 * @docs docs/succinct-indexable-dictionary.md
 */

#include <bits/stdc++.h>
using namespace std;

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