Range-Parallel DSU
(ds/dsu/range_parallel_dsu.hpp)

View this file on GitHub
Last update: 2026-07-13 06:05:18+09:00
Include: #include "ds/dsu/range_parallel_dsu.hpp"

Overview

RangeParallelDsu maintains connectivity among vertices 0, 1, ..., n - 1 and efficiently performs a parallel range merge:

merge(first, second, length)

adds the equivalences

first + offset == second + offset

for every 0 <= offset < length. Calling an ordinary DSU merge for every offset can take linear time per query; this structure shares completed work between queries.

Internally, one DSU is maintained for every relevant power-of-two block size. Two blocks are equivalent when all corresponding vertices in those blocks have already been merged. A general range is represented by two overlapping power-of-two blocks, and a newly merged block recursively activates its two halves. Each auxiliary state can be activated only once.

RangeParallelUnionFind is an alias for RangeParallelDsu.

Merge Callback

The callback overloads invoke

callback(new_leader, absorbed_leader);

once for every actual merge in the underlying vertex DSU. At that point:

new_leader is the leader of the combined component;
absorbed_leader was the other component’s leader immediately before the merge;
leader(absorbed_leader) == new_leader already holds.

This makes it possible to maintain component sums or other external aggregate state. The callback is not invoked for pairs that were already connected.

Store each aggregate at its component leader. Merge the two leader entries in the callback, and look up the current leader whenever the aggregate is queried:

std::vector<long long> sum = initial_values;

auto combine = [&](int new_leader, int absorbed_leader) {
    sum[new_leader] += sum[absorbed_leader];
};

dsu.merge(first, second, length, combine);
long long aggregate = sum[dsu.leader(vertex)];

After a merge, the entry at absorbed_leader is stale and must not be queried directly. It does not need to be cleared because that vertex cannot become a leader again. The callback can run multiple times during one range merge—once for each pair of previously distinct vertex components that becomes connected.

Every merge function returns the number of callback-producing vertex merges. The overloads without a callback perform the same connectivity changes and return the same count.

Interface

class RangeParallelDsu {
public:
    RangeParallelDsu();
    explicit RangeParallelDsu(int size);

    int size() const;
    bool empty() const;
    int component_count() const;

    int leader(int vertex);
    int leader(int vertex) const;
    bool same(int first, int second);
    bool same(int first, int second) const;
    int group_size(int vertex);
    int group_size(int vertex) const;

    template <class Callback>
    int merge(int first, int second, int length, Callback&& callback);
    int merge(int first, int second, int length);

    template <class Callback>
    int merge_ranges(
        int first_left,
        int first_right,
        int second_left,
        int second_right,
        Callback&& callback
    );
    int merge_ranges(
        int first_left,
        int first_right,
        int second_left,
        int second_right
    );

    template <class Callback>
    int merge(int first, int second, Callback&& callback);
    int merge(int first, int second);
};

The three-argument merge(first, second, length) merges the half-open ranges [first, first + length) and [second, second + length). merge_ranges accepts both half-open ranges explicitly and requires equal lengths. The two-argument merge(first, second) is an ordinary single-pair merge.

Complexity

Let $N$ be the number of vertices. Let $A$ be the number of previously unseen auxiliary power-of-two block equivalences activated by one range merge.

Method	Complexity
Construction	$O(N\log N)$ time and memory
`merge(first, second, length, callback)`	$O((A+1)\alpha(N))$ time
`merge_ranges(...)`	Same as the corresponding `merge`
Single-pair `merge(first, second)`	Amortized $O(\alpha(N))$
`leader`, `same`, `group_size`	Amortized $O(\alpha(N))$
`size`, `empty`, `component_count`	$O(1)$

Across the entire lifetime of the structure, the sum of $A$ is $O(N\log N)$. Therefore, $Q$ range merges take $O((N\log N + Q)\alpha(N))$ time in total, in addition to callback work. There are at most $N-1$ callback invocations over the lifetime of the object.

Preconditions

Indices are zero-based.
Both merged ranges must lie inside [0, size()).
length may be zero; such a merge does nothing and returns zero.
The two ranges may overlap or be identical.
merge_ranges requires equal range lengths.
Query methods do not allocate memory after construction.

Example

#include "ds/dsu/range_parallel_dsu.hpp"

#include <iostream>
#include <vector>

int main() {
    m1une::ds::RangeParallelDsu dsu(8);
    std::vector<int> sum = {1, 2, 3, 4, 5, 6, 7, 8};

    auto combine = [&](int new_leader, int absorbed_leader) {
        sum[new_leader] += sum[absorbed_leader];
    };
    auto component_sum = [&](int vertex) {
        return sum[dsu.leader(vertex)];
    };

    dsu.merge(0, 4, 4, combine);
    std::cout << dsu.same(2, 6) << '\n';  // 1
    std::cout << dsu.group_size(2) << '\n';  // 2
    std::cout << component_sum(2) << '\n';  // 3 + 7 = 10

    dsu.merge_ranges(0, 2, 2, 4, combine);
    std::cout << dsu.group_size(0) << '\n';  // 4
    std::cout << component_sum(4) << '\n';  // 1 + 3 + 5 + 7 = 16
}

Verified with

verify/ds/dsu/range_parallel_dsu.test.cpp

Code

#ifndef M1UNE_DS_DSU_RANGE_PARALLEL_DSU_HPP
#define M1UNE_DS_DSU_RANGE_PARALLEL_DSU_HPP 1

#include <bit>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

// Merges corresponding vertices of two equal-length ranges.
class RangeParallelDsu {
   private:
    struct LevelDsu {
        std::vector<int> parent_or_size;
        int component_count;

        explicit LevelDsu(int size = 0)
            : parent_or_size(std::size_t(size), -1), component_count(size) {}

        int leader(int vertex) {
            if (parent_or_size[vertex] < 0) return vertex;
            return parent_or_size[vertex] = leader(parent_or_size[vertex]);
        }

        int leader(int vertex) const {
            while (parent_or_size[vertex] >= 0) {
                vertex = parent_or_size[vertex];
            }
            return vertex;
        }

        std::pair<int, int> merge(int first, int second) {
            first = leader(first);
            second = leader(second);
            if (first == second) return {first, -1};
            if (-parent_or_size[first] < -parent_or_size[second]) {
                std::swap(first, second);
            }
            parent_or_size[first] += parent_or_size[second];
            parent_or_size[second] = first;
            component_count--;
            return {first, second};
        }
    };

    int _size;
    std::vector<LevelDsu> _levels;

    static int check_size(int size) {
        assert(size >= 0);
        return size;
    }

    void check_vertex(int vertex) const {
        assert(0 <= vertex && vertex < _size);
    }

    void check_range(int first, int length) const {
        assert(0 <= first && 0 <= length);
        assert(length <= _size);
        assert(first <= _size - length);
    }

    template <class Callback>
    int merge_block(int level, int first, int second, Callback& callback) {
        std::pair<int, int> merged = _levels[level].merge(first, second);
        if (merged.second == -1) return 0;
        if (level == 0) {
            callback(merged.first, merged.second);
            return 1;
        }

        const int half = 1 << (level - 1);
        int result = merge_block(level - 1, first, second, callback);
        result += merge_block(level - 1, first + half, second + half, callback);
        return result;
    }

   public:
    RangeParallelDsu() : RangeParallelDsu(0) {}

    explicit RangeParallelDsu(int size) : _size(check_size(size)) {
        _levels.emplace_back(_size);
        for (int block_size = 2; block_size < _size; block_size *= 2) {
            _levels.emplace_back(_size - block_size + 1);
            if (block_size > _size / 2) break;
        }
    }

    int size() const {
        return _size;
    }

    bool empty() const {
        return _size == 0;
    }

    int component_count() const {
        return _levels[0].component_count;
    }

    int leader(int vertex) {
        check_vertex(vertex);
        return _levels[0].leader(vertex);
    }

    int leader(int vertex) const {
        check_vertex(vertex);
        return _levels[0].leader(vertex);
    }

    bool same(int first, int second) {
        return leader(first) == leader(second);
    }

    bool same(int first, int second) const {
        return leader(first) == leader(second);
    }

    int group_size(int vertex) {
        return -_levels[0].parent_or_size[leader(vertex)];
    }

    int group_size(int vertex) const {
        return -_levels[0].parent_or_size[leader(vertex)];
    }

    template <class Callback>
    int merge(int first, int second, int length, Callback&& callback) {
        check_range(first, length);
        check_range(second, length);
        if (length == 0) return 0;
        if (length == 1) {
            return merge_block(0, first, second, callback);
        }

        const int level = int(std::bit_width(unsigned(length - 1))) - 1;
        const int block_size = 1 << level;
        int result = merge_block(level, first, second, callback);
        result += merge_block(level, first + length - block_size,
                              second + length - block_size, callback);
        return result;
    }

    int merge(int first, int second, int length) {
        auto ignore = [](int, int) {};
        return merge(first, second, length, ignore);
    }

    template <class Callback>
    int merge_ranges(int first_left, int first_right, int second_left,
                     int second_right, Callback&& callback) {
        assert(first_right - first_left == second_right - second_left);
        return merge(first_left, second_left, first_right - first_left,
                     std::forward<Callback>(callback));
    }

    int merge_ranges(int first_left, int first_right, int second_left,
                     int second_right) {
        auto ignore = [](int, int) {};
        return merge_ranges(first_left, first_right, second_left, second_right,
                            ignore);
    }

    template <class Callback>
    int merge(int first, int second, Callback&& callback) {
        check_vertex(first);
        check_vertex(second);
        return merge_block(0, first, second, callback);
    }

    int merge(int first, int second) {
        auto ignore = [](int, int) {};
        return merge(first, second, ignore);
    }
};

using RangeParallelUnionFind = RangeParallelDsu;

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_DSU_RANGE_PARALLEL_DSU_HPP

#line 1 "ds/dsu/range_parallel_dsu.hpp"



#include <bit>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

namespace m1une {
namespace ds {

// Merges corresponding vertices of two equal-length ranges.
class RangeParallelDsu {
   private:
    struct LevelDsu {
        std::vector<int> parent_or_size;
        int component_count;

        explicit LevelDsu(int size = 0)
            : parent_or_size(std::size_t(size), -1), component_count(size) {}

        int leader(int vertex) {
            if (parent_or_size[vertex] < 0) return vertex;
            return parent_or_size[vertex] = leader(parent_or_size[vertex]);
        }

        int leader(int vertex) const {
            while (parent_or_size[vertex] >= 0) {
                vertex = parent_or_size[vertex];
            }
            return vertex;
        }

        std::pair<int, int> merge(int first, int second) {
            first = leader(first);
            second = leader(second);
            if (first == second) return {first, -1};
            if (-parent_or_size[first] < -parent_or_size[second]) {
                std::swap(first, second);
            }
            parent_or_size[first] += parent_or_size[second];
            parent_or_size[second] = first;
            component_count--;
            return {first, second};
        }
    };

    int _size;
    std::vector<LevelDsu> _levels;

    static int check_size(int size) {
        assert(size >= 0);
        return size;
    }

    void check_vertex(int vertex) const {
        assert(0 <= vertex && vertex < _size);
    }

    void check_range(int first, int length) const {
        assert(0 <= first && 0 <= length);
        assert(length <= _size);
        assert(first <= _size - length);
    }

    template <class Callback>
    int merge_block(int level, int first, int second, Callback& callback) {
        std::pair<int, int> merged = _levels[level].merge(first, second);
        if (merged.second == -1) return 0;
        if (level == 0) {
            callback(merged.first, merged.second);
            return 1;
        }

        const int half = 1 << (level - 1);
        int result = merge_block(level - 1, first, second, callback);
        result += merge_block(level - 1, first + half, second + half, callback);
        return result;
    }

   public:
    RangeParallelDsu() : RangeParallelDsu(0) {}

    explicit RangeParallelDsu(int size) : _size(check_size(size)) {
        _levels.emplace_back(_size);
        for (int block_size = 2; block_size < _size; block_size *= 2) {
            _levels.emplace_back(_size - block_size + 1);
            if (block_size > _size / 2) break;
        }
    }

    int size() const {
        return _size;
    }

    bool empty() const {
        return _size == 0;
    }

    int component_count() const {
        return _levels[0].component_count;
    }

    int leader(int vertex) {
        check_vertex(vertex);
        return _levels[0].leader(vertex);
    }

    int leader(int vertex) const {
        check_vertex(vertex);
        return _levels[0].leader(vertex);
    }

    bool same(int first, int second) {
        return leader(first) == leader(second);
    }

    bool same(int first, int second) const {
        return leader(first) == leader(second);
    }

    int group_size(int vertex) {
        return -_levels[0].parent_or_size[leader(vertex)];
    }

    int group_size(int vertex) const {
        return -_levels[0].parent_or_size[leader(vertex)];
    }

    template <class Callback>
    int merge(int first, int second, int length, Callback&& callback) {
        check_range(first, length);
        check_range(second, length);
        if (length == 0) return 0;
        if (length == 1) {
            return merge_block(0, first, second, callback);
        }

        const int level = int(std::bit_width(unsigned(length - 1))) - 1;
        const int block_size = 1 << level;
        int result = merge_block(level, first, second, callback);
        result += merge_block(level, first + length - block_size,
                              second + length - block_size, callback);
        return result;
    }

    int merge(int first, int second, int length) {
        auto ignore = [](int, int) {};
        return merge(first, second, length, ignore);
    }

    template <class Callback>
    int merge_ranges(int first_left, int first_right, int second_left,
                     int second_right, Callback&& callback) {
        assert(first_right - first_left == second_right - second_left);
        return merge(first_left, second_left, first_right - first_left,
                     std::forward<Callback>(callback));
    }

    int merge_ranges(int first_left, int first_right, int second_left,
                     int second_right) {
        auto ignore = [](int, int) {};
        return merge_ranges(first_left, first_right, second_left, second_right,
                            ignore);
    }

    template <class Callback>
    int merge(int first, int second, Callback&& callback) {
        check_vertex(first);
        check_vertex(second);
        return merge_block(0, first, second, callback);
    }

    int merge(int first, int second) {
        auto ignore = [](int, int) {};
        return merge(first, second, ignore);
    }
};

using RangeParallelUnionFind = RangeParallelDsu;

}  // namespace ds
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Range-Parallel DSU
(ds/dsu/range_parallel_dsu.hpp)

Overview

Merge Callback

Interface

Complexity

Preconditions

Example

Verified with

Code

Range-Parallel DSU (ds/dsu/range_parallel_dsu.hpp)

Overview

Merge Callback

Interface

Complexity

Preconditions

Example

Verified with

Code

Range-Parallel DSU
(ds/dsu/range_parallel_dsu.hpp)