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

• View this file on GitHub
• Last update: 2024-02-25 18:15:39+09:00
• Include: #include "data_structure/enumerate_segment_tree_nodes.hpp"

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

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

使用例

• ABC342 G
  • Dual Segment Tree における作用素を std::multiset を用いて陽にすべて持っておくことで Undo 操作を実現している

Code

#pragma once

#include <vector>

// Segment Tree において区間 [l, r) をカバーする区間のノード番号を出力
// 区間の位置が小さい順に(左から)出力
// size は SegmentTree の size と同じ
std::vector<int> enumerate_segment_tree_range_covering_nodes(const int size, int l, int r) {
    std::vector<int> 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;
}

// Segment Tree において区間 [p, p + 1) が含まれる区間のノード番号を出力
// 区間の幅が小さい順に(下から)出力
// size は SegmentTree の size と同じ
std::vector<int> enumerate_segment_tree_point_containing_nodes(const int size, int p) {
    p += size;
    std::vector<int> ret;
    for (int i = 0; (1 << i) <= size; i++) ret.push_back(p >> i);
    return ret;
}

#line 2 "data_structure/enumerate_segment_tree_nodes.hpp"

#include <vector>

// Segment Tree において区間 [l, r) をカバーする区間のノード番号を出力
// 区間の位置が小さい順に(左から)出力
// size は SegmentTree の size と同じ
std::vector<int> enumerate_segment_tree_range_covering_nodes(const int size, int l, int r) {
    std::vector<int> 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;
}

// Segment Tree において区間 [p, p + 1) が含まれる区間のノード番号を出力
// 区間の幅が小さい順に(下から)出力
// size は SegmentTree の size と同じ
std::vector<int> enumerate_segment_tree_point_containing_nodes(const int size, int p) {
    p += size;
    std::vector<int> ret;
    for (int i = 0; (1 << i) <= size; i++) ret.push_back(p >> i);
    return ret;
}

Back to top page