bit vector

ソースコード

  1#pragma once
  2#include <iostream>
  3#include <vector>
  4#include <cassert>
  5using namespace std;
  6
  7// BitVector
  8namespace titan23 {
  9
 10    class BitVector {
 11      private:
 12        using u64 = unsigned long long;
 13        int n, bsize;
 14        vector<u64> bit, acc;
 15
 16      public:
 17        BitVector() {}
 18        BitVector(const int n) :
 19            n(n), bsize((n+63)>>6), bit(bsize+1, 0), acc(bsize+1, 0) {}
 20
 21        void set(const int k) {
 22            bit[k>>6] |= (1ull) << (k & 63);
 23        }
 24
 25        void build() {
 26            for (int i = 0; i < bsize; ++i) {
 27                acc[i+1] += acc[i] + __builtin_popcountll(bit[i]);
 28            }
 29        }
 30
 31        bool access(const int k) const {
 32            return (bit[k>>6] >> (k&63)) & 1;
 33        }
 34
 35        int rank0(const int r) const {
 36            return r - (acc[r>>6] + __builtin_popcountll(bit[r>>6] & ((1ull << (r & 63)) - 1)));
 37        }
 38
 39        int rank1(const int r) const {
 40            return acc[r>>6] + __builtin_popcountll(bit[r>>6] & ((1ull << (r & 63)) - 1));
 41        }
 42
 43        int rank(const int r, const bool v) const {
 44            return v ? rank1(r) : rank0(r);
 45        }
 46
 47        int select0(int k) const {
 48            if (k < 0 or rank0(n) <= k) return -1;
 49            int l = 0, r = bsize+1;
 50            while (r - l > 1) {
 51                const int m = (l + r) >> 1;
 52                if (m*32 - acc[m] > k) {
 53                    r = m;
 54                } else {
 55                    l = m;
 56                }
 57            }
 58            int indx = 32 * l;
 59            k = k - (l*32 - acc[l]) + rank0(indx);
 60            l = indx; r = indx+32;
 61            while (r - l > 1) {
 62                const int m = (l + r) >> 1;
 63                if (rank0(m) > k) {
 64                    r = m;
 65                } else {
 66                    l = m;
 67                }
 68            }
 69            return l;
 70        }
 71
 72        int select1(int k) const {
 73            if (k < 0 || rank1(n) <= k) return -1;
 74            int l = 0, r = bsize+1;
 75            while (r - l > 1) {
 76                const int m = (l + r) >> 1;
 77                if (acc[m] > k) {
 78                    r = m;
 79                } else {
 80                    l = m;
 81                }
 82            }
 83            int indx = 32 * l;
 84            k = k - acc[l] + rank1(indx);
 85            l = indx; r = indx+32;
 86            while (r - l > 1) {
 87                const int m = (l + r) >> 1;
 88                if (rank1(m) > k) {
 89                    r = m;
 90                } else {
 91                    l = m;
 92                }
 93            }
 94            return l;
 95        }
 96
 97        int select(const int k, const int v) const {
 98            return v ? select1(k) : select0(k);
 99        }
100
101        int len() const {
102            return n;
103        }
104
105        void print() const {
106            cout << "[";
107            for (int i = 0; i < len()-1; ++i) {
108                cout << access(i) << ", ";
109            }
110            if (len() > 0) {
111                cout << access(len()-1);
112            }
113            cout << "]\n";
114        }
115    };
116}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/bit_vector.cpp