Parallel Binary Search
(algo/offline/parallel_binary_search.hpp)

• View this file on GitHub
• Last update: 2026-07-07 22:10:04+09:00
• Include: #include "algo/offline/parallel_binary_search.hpp"

Overview

parallel_binary_search solves many monotone prefix-decision queries at once. It repeatedly resets a mutable state, applies events in increasing order, and checks the queries whose current midpoint is that prefix length.

The public namespace is m1une::algo.

Function

template <class Apply, class Check, class Reset>
std::vector<int> parallel_binary_search(
    int query_count,
    int event_count,
    Apply apply,
    Check check,
    Reset reset
);

For each query, the return value is the minimum k such that the query is true after applying events [0, k). If a query is never true, its answer is event_count + 1.

Callbacks:

Callback	Meaning
reset()	Clears the mutable state to the zero-event state.
apply(event)	Applies event event; events are passed in increasing order inside each round.
check(query)	Returns whether query query is true in the current state.

The complexity is $O((E + Q)\log(E + 1))$ callback invocations, where $E$ is event_count and $Q$ is query_count.

Example

#include "algo/offline/parallel_binary_search.hpp"

#include <vector>

int main() {
    std::vector<int> add = {3, 1, 4};
    std::vector<int> need = {0, 4, 9};
    int current = 0;

    std::vector<int> answer = m1une::algo::parallel_binary_search(
        int(need.size()),
        int(add.size()),
        [&](int event) {
            current += add[event];
        },
        [&](int query) {
            return need[query] <= current;
        },
        [&]() {
            current = 0;
        }
    );
}

Required by

• Algorithms All (algo/all.hpp)
• Offline Algorithms All (algo/offline/all.hpp)

Verified with

• verify/algo/offline/parallel_binary_search.test.cpp

Code

#ifndef M1UNE_ALGO_OFFLINE_PARALLEL_BINARY_SEARCH_HPP
#define M1UNE_ALGO_OFFLINE_PARALLEL_BINARY_SEARCH_HPP 1

#include <cassert>
#include <vector>

namespace m1une {
namespace algo {

template <class Apply, class Check, class Reset>
std::vector<int> parallel_binary_search(
    int query_count,
    int event_count,
    Apply apply,
    Check check,
    Reset reset
) {
    assert(0 <= query_count);
    assert(0 <= event_count);

    std::vector<int> low(query_count, -1);
    std::vector<int> high(query_count, event_count + 1);
    std::vector<std::vector<int>> bucket(event_count + 1);

    while (true) {
        bool active = false;
        for (auto& queries : bucket) queries.clear();

        for (int query = 0; query < query_count; ++query) {
            if (high[query] - low[query] <= 1) continue;
            const int middle = low[query] + (high[query] - low[query]) / 2;
            bucket[middle].push_back(query);
            active = true;
        }
        if (!active) break;

        reset();
        int applied = 0;
        for (int middle = 0; middle <= event_count; ++middle) {
            while (applied < middle) {
                apply(applied);
                ++applied;
            }
            for (int query : bucket[middle]) {
                if (check(query)) {
                    high[query] = middle;
                } else {
                    low[query] = middle;
                }
            }
        }
    }

    return high;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_OFFLINE_PARALLEL_BINARY_SEARCH_HPP

#line 1 "algo/offline/parallel_binary_search.hpp"



#include <cassert>
#include <vector>

namespace m1une {
namespace algo {

template <class Apply, class Check, class Reset>
std::vector<int> parallel_binary_search(
    int query_count,
    int event_count,
    Apply apply,
    Check check,
    Reset reset
) {
    assert(0 <= query_count);
    assert(0 <= event_count);

    std::vector<int> low(query_count, -1);
    std::vector<int> high(query_count, event_count + 1);
    std::vector<std::vector<int>> bucket(event_count + 1);

    while (true) {
        bool active = false;
        for (auto& queries : bucket) queries.clear();

        for (int query = 0; query < query_count; ++query) {
            if (high[query] - low[query] <= 1) continue;
            const int middle = low[query] + (high[query] - low[query]) / 2;
            bucket[middle].push_back(query);
            active = true;
        }
        if (!active) break;

        reset();
        int applied = 0;
        for (int middle = 0; middle <= event_count; ++middle) {
            while (applied < middle) {
                apply(applied);
                ++applied;
            }
            for (int query : bucket[middle]) {
                if (check(query)) {
                    high[query] = middle;
                } else {
                    low[query] = middle;
                }
            }
        }
    }

    return high;
}

}  // namespace algo
}  // namespace m1une

Back to top page