Range Edge Graph
(graph/range_edge_graph.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/range_edge_graph.hpp"

Overview

RangeEdgeGraph<T> compactly represents directed edges whose endpoints are points or contiguous ranges. It supports operations such as:

add an edge from one point to every point in a range;
add an edge from every point in a range to one point;
add an edge from every point in one range to every point in another range.

Adding all conceptual edges explicitly can require quadratic space. RangeEdgeGraph uses two segment-tree-shaped directed graphs and auxiliary vertices, reducing each range operation to $O(\log N)$ actual edges.

This is the “representing intervals as edges” technique used in problems such as AtCoder ABC414 G and Codeforces 786B.

The represented graph is an ordinary Graph<T>, so it can be passed directly to dijkstra, bellman_ford, or other compatible graph algorithms. Edge costs added by this class may be arbitrary values of T; choose a shortest-path algorithm that supports those costs.

Vertex IDs

The original N point vertices always have IDs 0, 1, ..., N - 1. point_vertex(i) returns i.

The constructor adds internal segment-tree vertices after the original points. Range-to-range operations add one auxiliary vertex each. Therefore, use range_graph.graph().size() rather than range_graph.size() when iterating over every vertex in the expanded graph.

Method	Meaning
`size()`	Number of original point vertices.
`point_vertex(i)`	Expanded-graph vertex representing point `i`.
`add_vertex()`	Adds and returns a custom auxiliary vertex.
`graph()`	Returns the expanded `Graph<T>`.

Adding Edges

All ranges are half-open: [left, right).

Method	Conceptual edges added
`add_point_to_point(from, to, cost)`	`from -> to` with cost `cost`.
`add_point_to_range(from, left, right, cost)`	`from -> v` for every `v` in `[left, right)`, each with cost `cost`.
`add_range_to_point(left, right, to, cost)`	`v -> to` for every `v` in `[left, right)`, each with cost `cost`.
`add_range_to_range(from_left, from_right, to_left, to_right, cost)`	`u -> v` for every `u` in the first range and `v` in the second range, each with cost `cost`.

Empty ranges add no edges. add_range_to_range returns its auxiliary vertex, or -1 if either range is empty.

These methods add directed edges. To represent both directions, call the corresponding operation twice with the ranges reversed.

Canonical Range Nodes

Some problems need a cost that depends on the boundary of a canonical segment, as in the ABC414 G editorial. The following methods expose the $O(\log N)$ segment-tree nodes covering a range:

Method	Property of each returned vertex
`from_range_nodes(left, right)`	Every point in the node’s interval can reach the vertex with cost zero.
`to_range_nodes(left, right)`	The vertex can reach every point in the node’s interval with cost zero.

Both return std::vector<RangeEdgeNode>. Each node has:

Member	Meaning
`vertex`	Vertex ID in the expanded graph.
`left`, `right`	Half-open interval represented by that vertex.

The returned intervals are disjoint and partition the requested range. Custom edges can be added through graph().add_directed_edge.

Construction

For each segment-tree interval, the graph has two orientations:

On the from side, point edges lead upward from children to parents. Thus every point can reach each covering interval vertex.
On the to side, edges lead downward from parents to children. Thus each interval vertex can reach every point it contains.

All structural edges have cost zero. A range-to-range operation creates one auxiliary vertex, adds the requested cost while leaving the source-side cover, and then reaches the destination-side cover with zero-cost edges.

Complexity

Let N be the number of original points.

Operation	Added vertices	Added edges	Time
Constructor	At most $2N - 2$ internal	At most $4N - 4$	$O(N)$
Point to point	0	1	Amortized $O(1)$
Point to range	0	$O(\log N)$	$O(\log N)$
Range to point	0	$O(\log N)$	$O(\log N)$
Range to range	1	$O(\log N)$	$O(\log N)$
Either cover query	0	0	$O(\log N)$

After Q range-to-range additions, the expanded graph has $O(N + Q)$ vertices and $O(N + Q\log N)$ edges.

Example

#include "graph/dijkstra.hpp"
#include "graph/range_edge_graph.hpp"
#include <iostream>

int main() {
    m1une::graph::RangeEdgeGraph<long long> graph(6);

    // Every point in [0, 2) has an edge of cost 7 to every point in [3, 6).
    graph.add_range_to_range(0, 2, 3, 6, 7);

    auto result = m1une::graph::dijkstra(graph.graph(), 1);
    for (int i = 0; i < graph.size(); i++) {
        std::cout << result.dist[i] << "\n";
    }
}

Depends on

Graph (graph/graph.hpp)

Required by

Graph All (graph/all.hpp)

Verified with

Code

#ifndef M1UNE_GRAPH_RANGE_EDGE_GRAPH_HPP
#define M1UNE_GRAPH_RANGE_EDGE_GRAPH_HPP 1

#include <cassert>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct RangeEdgeNode {
    int vertex;
    int left;
    int right;
};

template <class T>
class RangeEdgeGraph {
    struct SegmentNode {
        int left = 0;
        int right = 0;
        int from_vertex = -1;
        int to_vertex = -1;
    };

    int _n;
    Graph<T> _graph;
    std::vector<SegmentNode> _segment;

    void assert_point(int point) const {
        (void)point;
        assert(0 <= point && point < _n);
    }

    void assert_range(int left, int right) const {
        (void)left;
        (void)right;
        assert(0 <= left && left <= right && right <= _n);
    }

    void build(int node, int left, int right) {
        _segment[node].left = left;
        _segment[node].right = right;
        if (right - left == 1) {
            _segment[node].from_vertex = left;
            _segment[node].to_vertex = left;
            return;
        }

        int middle = (left + right) / 2;
        build(node * 2, left, middle);
        build(node * 2 + 1, middle, right);

        int from_vertex = _graph.add_vertex();
        int to_vertex = _graph.add_vertex();
        _segment[node].from_vertex = from_vertex;
        _segment[node].to_vertex = to_vertex;

        _graph.add_directed_edge(_segment[node * 2].from_vertex, from_vertex, T());
        _graph.add_directed_edge(_segment[node * 2 + 1].from_vertex, from_vertex, T());
        _graph.add_directed_edge(to_vertex, _segment[node * 2].to_vertex, T());
        _graph.add_directed_edge(to_vertex, _segment[node * 2 + 1].to_vertex, T());
    }

    void collect(int node, int left, int right, bool from_side,
                 std::vector<RangeEdgeNode>& result) const {
        const auto& current = _segment[node];
        if (right <= current.left || current.right <= left) return;
        if (left <= current.left && current.right <= right) {
            int vertex = from_side ? current.from_vertex : current.to_vertex;
            result.push_back(RangeEdgeNode{vertex, current.left, current.right});
            return;
        }
        collect(node * 2, left, right, from_side, result);
        collect(node * 2 + 1, left, right, from_side, result);
    }

   public:
    RangeEdgeGraph() : RangeEdgeGraph(0) {}

    explicit RangeEdgeGraph(int point_count)
        : _n(point_count),
          _graph(point_count),
          _segment(point_count == 0 ? 1 : point_count * 4) {
        assert(point_count >= 0);
        if (point_count != 0) build(1, 0, point_count);
    }

    int size() const {
        return _n;
    }

    int point_vertex(int point) const {
        assert_point(point);
        return point;
    }

    int add_vertex() {
        return _graph.add_vertex();
    }

    Graph<T>& graph() {
        return _graph;
    }

    const Graph<T>& graph() const {
        return _graph;
    }

    std::vector<RangeEdgeNode> from_range_nodes(int left, int right) const {
        assert_range(left, right);
        std::vector<RangeEdgeNode> result;
        if (left != right) collect(1, left, right, true, result);
        return result;
    }

    std::vector<RangeEdgeNode> to_range_nodes(int left, int right) const {
        assert_range(left, right);
        std::vector<RangeEdgeNode> result;
        if (left != right) collect(1, left, right, false, result);
        return result;
    }

    int add_point_to_point(int from, int to, T cost) {
        assert_point(from);
        assert_point(to);
        return _graph.add_directed_edge(from, to, cost);
    }

    void add_point_to_range(int from, int left, int right, T cost) {
        assert_point(from);
        for (const auto& node : to_range_nodes(left, right)) {
            _graph.add_directed_edge(from, node.vertex, cost);
        }
    }

    void add_range_to_point(int left, int right, int to, T cost) {
        assert_point(to);
        for (const auto& node : from_range_nodes(left, right)) {
            _graph.add_directed_edge(node.vertex, to, cost);
        }
    }

    int add_range_to_range(int from_left, int from_right, int to_left, int to_right,
                           T cost) {
        assert_range(from_left, from_right);
        assert_range(to_left, to_right);
        if (from_left == from_right || to_left == to_right) return -1;

        int auxiliary = add_vertex();
        for (const auto& node : from_range_nodes(from_left, from_right)) {
            _graph.add_directed_edge(node.vertex, auxiliary, cost);
        }
        for (const auto& node : to_range_nodes(to_left, to_right)) {
            _graph.add_directed_edge(auxiliary, node.vertex, T());
        }
        return auxiliary;
    }
};

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_RANGE_EDGE_GRAPH_HPP

#line 1 "graph/range_edge_graph.hpp"



#include <cassert>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 6 "graph/graph.hpp"
#include <utility>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

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

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 8 "graph/range_edge_graph.hpp"

namespace m1une {
namespace graph {

struct RangeEdgeNode {
    int vertex;
    int left;
    int right;
};

template <class T>
class RangeEdgeGraph {
    struct SegmentNode {
        int left = 0;
        int right = 0;
        int from_vertex = -1;
        int to_vertex = -1;
    };

    int _n;
    Graph<T> _graph;
    std::vector<SegmentNode> _segment;

    void assert_point(int point) const {
        (void)point;
        assert(0 <= point && point < _n);
    }

    void assert_range(int left, int right) const {
        (void)left;
        (void)right;
        assert(0 <= left && left <= right && right <= _n);
    }

    void build(int node, int left, int right) {
        _segment[node].left = left;
        _segment[node].right = right;
        if (right - left == 1) {
            _segment[node].from_vertex = left;
            _segment[node].to_vertex = left;
            return;
        }

        int middle = (left + right) / 2;
        build(node * 2, left, middle);
        build(node * 2 + 1, middle, right);

        int from_vertex = _graph.add_vertex();
        int to_vertex = _graph.add_vertex();
        _segment[node].from_vertex = from_vertex;
        _segment[node].to_vertex = to_vertex;

        _graph.add_directed_edge(_segment[node * 2].from_vertex, from_vertex, T());
        _graph.add_directed_edge(_segment[node * 2 + 1].from_vertex, from_vertex, T());
        _graph.add_directed_edge(to_vertex, _segment[node * 2].to_vertex, T());
        _graph.add_directed_edge(to_vertex, _segment[node * 2 + 1].to_vertex, T());
    }

    void collect(int node, int left, int right, bool from_side,
                 std::vector<RangeEdgeNode>& result) const {
        const auto& current = _segment[node];
        if (right <= current.left || current.right <= left) return;
        if (left <= current.left && current.right <= right) {
            int vertex = from_side ? current.from_vertex : current.to_vertex;
            result.push_back(RangeEdgeNode{vertex, current.left, current.right});
            return;
        }
        collect(node * 2, left, right, from_side, result);
        collect(node * 2 + 1, left, right, from_side, result);
    }

   public:
    RangeEdgeGraph() : RangeEdgeGraph(0) {}

    explicit RangeEdgeGraph(int point_count)
        : _n(point_count),
          _graph(point_count),
          _segment(point_count == 0 ? 1 : point_count * 4) {
        assert(point_count >= 0);
        if (point_count != 0) build(1, 0, point_count);
    }

    int size() const {
        return _n;
    }

    int point_vertex(int point) const {
        assert_point(point);
        return point;
    }

    int add_vertex() {
        return _graph.add_vertex();
    }

    Graph<T>& graph() {
        return _graph;
    }

    const Graph<T>& graph() const {
        return _graph;
    }

    std::vector<RangeEdgeNode> from_range_nodes(int left, int right) const {
        assert_range(left, right);
        std::vector<RangeEdgeNode> result;
        if (left != right) collect(1, left, right, true, result);
        return result;
    }

    std::vector<RangeEdgeNode> to_range_nodes(int left, int right) const {
        assert_range(left, right);
        std::vector<RangeEdgeNode> result;
        if (left != right) collect(1, left, right, false, result);
        return result;
    }

    int add_point_to_point(int from, int to, T cost) {
        assert_point(from);
        assert_point(to);
        return _graph.add_directed_edge(from, to, cost);
    }

    void add_point_to_range(int from, int left, int right, T cost) {
        assert_point(from);
        for (const auto& node : to_range_nodes(left, right)) {
            _graph.add_directed_edge(from, node.vertex, cost);
        }
    }

    void add_range_to_point(int left, int right, int to, T cost) {
        assert_point(to);
        for (const auto& node : from_range_nodes(left, right)) {
            _graph.add_directed_edge(node.vertex, to, cost);
        }
    }

    int add_range_to_range(int from_left, int from_right, int to_left, int to_right,
                           T cost) {
        assert_range(from_left, from_right);
        assert_range(to_left, to_right);
        if (from_left == from_right || to_left == to_right) return -1;

        int auxiliary = add_vertex();
        for (const auto& node : from_range_nodes(from_left, from_right)) {
            _graph.add_directed_edge(node.vertex, auxiliary, cost);
        }
        for (const auto& node : to_range_nodes(to_left, to_right)) {
            _graph.add_directed_edge(auxiliary, node.vertex, T());
        }
        return auxiliary;
    }
};

}  // namespace graph
}  // namespace m1une

m1une's library

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

Range Edge Graph
(graph/range_edge_graph.hpp)

Overview

Vertex IDs

Adding Edges

Canonical Range Nodes

Construction

Complexity

Example

Depends on

Required by

Verified with

Code

Range Edge Graph (graph/range_edge_graph.hpp)

Overview

Vertex IDs

Adding Edges

Canonical Range Nodes

Construction

Complexity

Example

Depends on

Required by

Verified with

Code

Range Edge Graph
(graph/range_edge_graph.hpp)