Segment Tree Range Split
(algo/enumeration/segtree_range.hpp)

• View this file on GitHub
• Last update: 2026-07-14 01:43:56+09:00
• Include: #include "algo/enumeration/segtree_range.hpp"

Overview

split_segtree_range decomposes a half-open range into the maximal aligned power-of-two ranges used by a segment tree. The result is ordered from left to right, is disjoint, and has union exactly [left, right).

For example, [3, 13) is split into [3, 4), [4, 8), [8, 12), and [12, 13). These are precisely the maximal nodes contained in the query range of a perfect segment tree whose leaf count is any power of two at least right; the tree size does not need to be passed to the function.

Function

template <std::integral Int>
requires(!std::same_as<std::remove_cv_t<Int>, bool>)
std::vector<std::pair<Int, Int>> split_segtree_range(Int left, Int right);

Int may be any integral type except bool. Both endpoints must be nonnegative and must satisfy left <= right.

Function	Description	Complexity
split_segtree_range(left, right)	Returns the maximal segment-tree ranges covering [left, right).	$O(K)$ time and memory, where $K = O(\log(right - left + 1))$ is the number of returned ranges.

Every returned [a, b) has positive power-of-two length and a is divisible by b - a. No returned range can be replaced by its parent while remaining inside [left, right). An empty input range returns an empty vector.

The function does not mutate its arguments or any external state.

Example

#include "algo/enumeration/segtree_range.hpp"

#include <iostream>

int main() {
    for (auto [left, right] :
         m1une::algo::split_segtree_range(3, 13)) {
        std::cout << "[" << left << ", " << right << ")\n";
    }
}

Output:

[3, 4)
[4, 8)
[8, 12)
[12, 13)

Required by

• Algorithms All (algo/all.hpp)
• Enumeration Algorithms All (algo/enumeration/all.hpp)

Verified with

• verify/algo/enumeration/segtree_range.test.cpp

Code

#ifndef M1UNE_ALGO_ENUMERATION_SEGTREE_RANGE_HPP
#define M1UNE_ALGO_ENUMERATION_SEGTREE_RANGE_HPP 1

#include <bit>
#include <cassert>
#include <concepts>
#include <type_traits>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

// Splits [left, right) into maximal segment-tree ranges from left to right.
template <std::integral Int>
requires(!std::same_as<std::remove_cv_t<Int>, bool>)
std::vector<std::pair<Int, Int>> split_segtree_range(Int left, Int right) {
    if constexpr (std::signed_integral<Int>) assert(Int(0) <= left);
    assert(left <= right);
    if constexpr (std::signed_integral<Int>) {
        if (left < 0) return {};
    }
    if (right < left) return {};

    using UInt = std::make_unsigned_t<Int>;
    UInt position = static_cast<UInt>(left);
    const UInt end = static_cast<UInt>(right);
    std::vector<std::pair<Int, Int>> result;
    if (position == end) return result;
    result.reserve(2 * std::bit_width(end - position));

    while (position < end) {
        UInt length = std::bit_floor(end - position);
        if (position != 0) {
            const UInt alignment = position & (~position + UInt(1));
            if (alignment < length) length = alignment;
        }
        const UInt next = position + length;
        result.emplace_back(
            static_cast<Int>(position), static_cast<Int>(next)
        );
        position = next;
    }
    return result;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_ENUMERATION_SEGTREE_RANGE_HPP

#line 1 "algo/enumeration/segtree_range.hpp"



#include <bit>
#include <cassert>
#include <concepts>
#include <type_traits>
#include <utility>
#include <vector>

namespace m1une {
namespace algo {

// Splits [left, right) into maximal segment-tree ranges from left to right.
template <std::integral Int>
requires(!std::same_as<std::remove_cv_t<Int>, bool>)
std::vector<std::pair<Int, Int>> split_segtree_range(Int left, Int right) {
    if constexpr (std::signed_integral<Int>) assert(Int(0) <= left);
    assert(left <= right);
    if constexpr (std::signed_integral<Int>) {
        if (left < 0) return {};
    }
    if (right < left) return {};

    using UInt = std::make_unsigned_t<Int>;
    UInt position = static_cast<UInt>(left);
    const UInt end = static_cast<UInt>(right);
    std::vector<std::pair<Int, Int>> result;
    if (position == end) return result;
    result.reserve(2 * std::bit_width(end - position));

    while (position < end) {
        UInt length = std::bit_floor(end - position);
        if (position != 0) {
            const UInt alignment = position & (~position + UInt(1));
            if (alignment < length) length = alignment;
        }
        const UInt next = position + length;
        result.emplace_back(
            static_cast<Int>(position), static_cast<Int>(next)
        );
        position = next;
    }
    return result;
}

}  // namespace algo
}  // namespace m1une

Back to top page