Segment Tree の 1 点変更や区間総積を行う際にアクセスするノード番号の列挙
(segment_tree/enumerate_segment_tree_nodes.hpp)

• View this file on GitHub
• Last update: 2026-04-11 00:41:57+09:00
• Include: #include "segment_tree/enumerate_segment_tree_nodes.hpp"
• Link: https://atcoder.jp/contests/abc349/tasks/abc349_d
• Link: https://atcoder.jp/contests/abc355/tasks/abc355_e

使い方

Segment Tree の set や prod においてアクセスするノード番号を列挙する

Segment Tree の各ノードにデータ構造を乗せる際などに利用する

参考文献

• AtCoder Beginner Contest 342 G - Retroactive Range Chmax
  • Dual Segment Tree における作用素を ErasablePriorityQueue を用いてすべて持っておくことで Undo 操作を実現している
• AtCoder Beginner Contest 349 D - Divide Interval
  • 長さ $2^{60}$ の Segment Tree に区間 $[l, r)$ のクエリを投げたときにアクセスするノード番号を列挙する
  • segment_tree_node_to_range でノード番号から区間を求める
• AtCoder Beginner Contest 355 E - Guess the Sum
  • segment_tree_node_to_range でノード番号から区間を求める

Depends on

• Countl Zero (misc/countl_zero.hpp)
• Topbit (misc/topbit.hpp)

Verified with

• data_structure/test/erasable_priority_queue.test.cpp
• segment_tree/test/enumerate_segment_tree_nodes.test.cpp

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <vector>

#include "../misc/topbit.hpp"

// 長さ size (2べき) の Segment Tree において区間 [l, r)
// をカバーする区間のノード番号を返す 区間の位置が小さい順に (左から) 返す
template <class T>
std::vector<T> enumerate_segment_tree_range_covering_nodes(const T size,
                                                           T l,
                                                           T r) {
    std::vector<T> ret, ret_rev;
    l += size;
    r += size;
    while (l < r) {
        if (l & 1) ret.push_back(l++);
        if (r & 1) ret_rev.push_back(--r);
        l >>= 1;
        r >>= 1;
    }
    std::reverse(ret_rev.begin(), ret_rev.end());
    ret.insert(ret.end(), ret_rev.begin(), ret_rev.end());
    return ret;
}

// 長さ size (2べき) の Segment Tree において seg[p]
// が含まれる区間のノード番号を返す 区間の幅が小さい順に (下から) 返す
template <class T>
std::vector<T> enumerate_segment_tree_point_containing_nodes(const T size,
                                                             T p) {
    p += size;
    std::vector<T> ret;
    for (int i = 0; (1LL << i) <= size; i++) ret.push_back(p >> i);
    return ret;
}

// 長さ size (2べき) の Segment Tree においてノード番号 i に対応する区間 [l, r)
// を返す https://atcoder.jp/contests/abc349/tasks/abc349_d
// https://atcoder.jp/contests/abc355/tasks/abc355_e
template <class T>
std::pair<T, T> segment_tree_node_to_range(const T size, const T i) {
    assert(size > 0 and i > 0);
    // (1 << n) = size
    const int n = topbit(size);
    // i の最上位ビット
    const int topbiti = topbit(i);
    // [(2 ^ x) * y, (2 ^ x) * (y + 1))
    const int x = n - topbiti;
    const T y = i - (1LL << topbiti);
    return {(1LL << x) * y, (1LL << x) * (y + 1)};
}

#line 2 "segment_tree/enumerate_segment_tree_nodes.hpp"

#include <algorithm>
#include <cassert>
#include <vector>

#line 2 "misc/topbit.hpp"

#line 2 "misc/countl_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countl_zero
// (000, 001, 010, 011, 100) -> (32, 31, 30, 30, 29)
#if __cplusplus >= 202002L
using std::countl_zero;
#else
int countl_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_clz(x);
}
int countl_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_clzll(x);
}
#endif
int countl_zero(int x) { return countl_zero((unsigned int)(x)); }
int countl_zero(long long int x) {
    return countl_zero((unsigned long long int)(x));
}
#line 4 "misc/topbit.hpp"

// topbit
// (000, 001, 010, 011, 100) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - countl_zero(x); }
int topbit(unsigned int x) { return 31 - countl_zero(x); }
int topbit(long long int x) { return 63 - countl_zero(x); }
int topbit(unsigned long long int x) { return 63 - countl_zero(x); }
#line 8 "segment_tree/enumerate_segment_tree_nodes.hpp"

// 長さ size (2べき) の Segment Tree において区間 [l, r)
// をカバーする区間のノード番号を返す 区間の位置が小さい順に (左から) 返す
template <class T>
std::vector<T> enumerate_segment_tree_range_covering_nodes(const T size,
                                                           T l,
                                                           T r) {
    std::vector<T> ret, ret_rev;
    l += size;
    r += size;
    while (l < r) {
        if (l & 1) ret.push_back(l++);
        if (r & 1) ret_rev.push_back(--r);
        l >>= 1;
        r >>= 1;
    }
    std::reverse(ret_rev.begin(), ret_rev.end());
    ret.insert(ret.end(), ret_rev.begin(), ret_rev.end());
    return ret;
}

// 長さ size (2べき) の Segment Tree において seg[p]
// が含まれる区間のノード番号を返す 区間の幅が小さい順に (下から) 返す
template <class T>
std::vector<T> enumerate_segment_tree_point_containing_nodes(const T size,
                                                             T p) {
    p += size;
    std::vector<T> ret;
    for (int i = 0; (1LL << i) <= size; i++) ret.push_back(p >> i);
    return ret;
}

// 長さ size (2べき) の Segment Tree においてノード番号 i に対応する区間 [l, r)
// を返す https://atcoder.jp/contests/abc349/tasks/abc349_d
// https://atcoder.jp/contests/abc355/tasks/abc355_e
template <class T>
std::pair<T, T> segment_tree_node_to_range(const T size, const T i) {
    assert(size > 0 and i > 0);
    // (1 << n) = size
    const int n = topbit(size);
    // i の最上位ビット
    const int topbiti = topbit(i);
    // [(2 ^ x) * y, (2 ^ x) * (y + 1))
    const int x = n - topbiti;
    const T y = i - (1LL << topbiti);
    return {(1LL << x) * y, (1LL << x) * (y + 1)};
}

Back to top page