data_structure/wavelet_matrix/small.hpp

• View this file on GitHub
• Last update: 2025-05-04 19:54:26+09:00
• Include: #include "data_structure/wavelet_matrix/small.hpp"

Depends on

• data_structure/wavelet_matrix.hpp

Verified with

• test/range_kth_smallest.test.cpp

Code

#pragma once
#include <data_structure/wavelet_matrix.hpp>

template <typename T>
T WaveletMatrix<T>::small(int l, int r, int p) {
    for (int i = 0; i < m; ++i) {
        int cnt = b[i].rank0(r) - b[i].rank0(l);
        if (cnt <= p) {
            p -= cnt;
            l = b[i].zeros + b[i].rank1(l);
            r = b[i].zeros + b[i].rank1(r);
        } else {
            l = b[i].rank0(l);
            r = b[i].rank0(r);
        }
    }
    return v[l];
}

#line 2 "data_structure/wavelet_matrix/small.hpp"
#include <data_structure/wavelet_matrix.hpp>

template <typename T>
T WaveletMatrix<T>::small(int l, int r, int p) {
    for (int i = 0; i < m; ++i) {
        int cnt = b[i].rank0(r) - b[i].rank0(l);
        if (cnt <= p) {
            p -= cnt;
            l = b[i].zeros + b[i].rank1(l);
            r = b[i].zeros + b[i].rank1(r);
        } else {
            l = b[i].rank0(l);
            r = b[i].rank0(r);
        }
    }
    return v[l];
}

Back to top page