Tree Cumulative Sum
(graph/tree/cumulative_sum.hpp)

View this file on GitHub
Last update: 2026-08-29 18:27:41+09:00
Include: #include "graph/tree/cumulative_sum.hpp"

Overview

TreeCumulativeSum<T> preprocesses static values on the vertices of a rooted tree. It stores the cumulative sum from the root to every vertex, then combines two root paths at their lowest common ancestor to answer any vertex-path sum.

TreeEdgeCumulativeSum<T> is the edge-valued variant. Its input vector is indexed by graph edge id, and its path sums exclude vertices and include exactly the edges on the path.

The underlying TreeCumulativeProduct<Group> and TreeEdgeCumulativeProduct<Group> types provide the same operations for any commutative group, such as xor. The additive wrappers use m1une::monoid::Add<T>.

#include "graph/graph.hpp"
#include "graph/tree/cumulative_sum.hpp"

Requirements and Behavior

The graph must be an undirected tree consisting of active edges. Vertex values must have size graph.size(). Edge values must have size graph.edge_count() and are looked up using the ids returned by add_edge. Indices are zero-based.

For TreeCumulativeProduct<Group>, Group must satisfy m1une::monoid::IsCommutativeGroup: it supplies value_type, id(), op(a, b), and inv(a). Associativity, commutativity, the identity law, and the inverse law are semantic requirements.

Construction does not mutate the graph or the input values. The values are static; rebuild the object after changing them.

Types

Type	Values represented
`TreeCumulativeProduct<Group>`	A group value on every vertex.
`TreeEdgeCumulativeProduct<Group>`	A group value for every graph edge id.
`TreeCumulativeSum<T>`	A numeric value on every vertex.
`TreeEdgeCumulativeSum<T>`	A numeric value for every graph edge id.

Interface

The following methods are shared by all four types. value_type is T for the sum wrappers and Group::value_type for the product types.

Method	Exact signature	Description	Complexity
Default constructor	`TreeCumulativeProduct()` or `TreeCumulativeSum()`	Constructs an empty object.	$O(1)$
Constructor	`TreeCumulativeProduct(const Graph<EdgeCost>& graph, const std::vector<value_type>& values, int root = 0)`	Builds cumulative products from `root`.	$O(N)$ time and space
Constructor	`TreeCumulativeSum(const Graph<EdgeCost>& graph, const std::vector<T>& values, int root = 0)`	Builds cumulative sums from `root`.	$O(N)$ time and space
`build`	`void build(const Graph<EdgeCost>& graph, const std::vector<value_type>& values, int root = 0)`	Rebuilds the object.	$O(N)$ time and space
`size`	`int size() const`	Returns the number of vertices.	$O(1)$
`empty`	`bool empty() const`	Returns whether there are no vertices.	$O(1)$
`root`	`int root() const`	Returns the selected root, or `-1` when empty.	$O(1)$
`lca`	`int lca(int first, int second) const`	Returns the lowest common ancestor under the selected root.	$O(\log N)$
`prod`	`value_type prod(int vertex) const`	Returns the product on the root-to-`vertex` path.	$O(1)$
`prod`	`value_type prod(int first, int second) const`	Returns the product on the simple path between the vertices.	$O(\log N)$
`sum`	`T sum(int vertex) const`	Additive wrapper for the root-to-`vertex` sum.	$O(1)$
`sum`	`T sum(int first, int second) const`	Additive wrapper for the simple-path sum.	$O(\log N)$

For vertex values, both endpoints of a path are included. In particular, sum(v, v) is the value at v. For edge values, sum(v, v) is zero, and sum(root, v) contains the edges strictly below the root on that path.

Choose T large enough to hold every root-path sum and the intermediate values formed while combining two prefixes.

Example

#include "graph/graph.hpp"
#include "graph/tree/cumulative_sum.hpp"

#include <iostream>
#include <vector>

int main() {
    m1une::graph::Graph<int> graph(5);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(1, 3);
    graph.add_edge(3, 4);

    std::vector<long long> value = {2, 3, 5, 7, 11};
    m1une::tree::TreeCumulativeSum<long long> sum(graph, value, 0);

    std::cout << sum.sum(4) << '\n';    // 2 + 3 + 7 + 11 = 23
    std::cout << sum.sum(2, 4) << '\n'; // 5 + 3 + 7 + 11 = 26
}

Depends on

Required by

Verified with

Code

#ifndef M1UNE_TREE_CUMULATIVE_SUM_HPP
#define M1UNE_TREE_CUMULATIVE_SUM_HPP 1

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

#include "../../monoid/add.hpp"
#include "../../monoid/concept.hpp"
#include "../graph.hpp"

namespace m1une {
namespace tree {

// Static cumulative products on root paths. Values are attached to vertices by
// default; set EdgeValues to true to index them by graph edge id instead.
template <m1une::monoid::IsCommutativeGroup Group, bool EdgeValues = false>
class TreeCumulativeProduct {
   public:
    using value_type = typename Group::value_type;

   private:
    int _n = 0;
    int _root = -1;
    std::vector<int> _parent;
    std::vector<int> _depth;
    std::vector<int> _head;
    std::vector<value_type> _prefix;

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

   public:
    TreeCumulativeProduct() = default;

    template <class EdgeCost>
    explicit TreeCumulativeProduct(
        const m1une::graph::Graph<EdgeCost>& graph,
        const std::vector<value_type>& values,
        int root = 0
    ) {
        build(graph, values, root);
    }

    template <class EdgeCost>
    void build(
        const m1une::graph::Graph<EdgeCost>& graph,
        const std::vector<value_type>& values,
        int root = 0
    ) {
        _n = graph.size();
        _root = _n == 0 ? -1 : root;
        assert(
            int(values.size())
            == (EdgeValues ? graph.edge_count() : graph.size())
        );

        _parent.assign(_n, -2);
        _depth.assign(_n, 0);
        _head.assign(_n, -1);
        _prefix.assign(_n, Group::id());
        if (_n == 0) return;
        assert(0 <= root && root < _n);

        std::vector<int> parent_edge(_n, -1);
        std::vector<int> order;
        order.reserve(_n);
        std::vector<int> stack = {root};
        _parent[root] = -1;
        while (!stack.empty()) {
            int vertex = stack.back();
            stack.pop_back();
            order.push_back(vertex);
            for (const auto& edge : graph[vertex]) {
                if (!edge.alive || _parent[edge.to] != -2) continue;
                _parent[edge.to] = vertex;
                parent_edge[edge.to] = edge.id;
                _depth[edge.to] = _depth[vertex] + 1;
                stack.push_back(edge.to);
            }
        }
        assert(int(order.size()) == _n);

        std::vector<int> subtree_size(_n, 1);
        std::vector<int> heavy(_n, -1);
        for (int index = _n - 1; index > 0; index--) {
            int vertex = order[index];
            int parent = _parent[vertex];
            subtree_size[parent] += subtree_size[vertex];
            if (
                heavy[parent] == -1
                || subtree_size[heavy[parent]] < subtree_size[vertex]
            ) {
                heavy[parent] = vertex;
            }
        }

        std::vector<std::pair<int, int>> starts;
        starts.emplace_back(root, root);
        while (!starts.empty()) {
            auto [start, head] = starts.back();
            starts.pop_back();
            for (
                int vertex = start;
                vertex != -1;
                vertex = heavy[vertex]
            ) {
                _head[vertex] = head;
                for (const auto& edge : graph[vertex]) {
                    if (
                        edge.alive && _parent[edge.to] == vertex
                        && edge.to != heavy[vertex]
                    ) {
                        starts.emplace_back(edge.to, edge.to);
                    }
                }
            }
        }

        if constexpr (!EdgeValues) _prefix[root] = values[root];
        for (int vertex : order) {
            if (vertex == root) continue;
            if constexpr (EdgeValues) {
                assert(0 <= parent_edge[vertex]);
                _prefix[vertex] = Group::op(
                    _prefix[_parent[vertex]],
                    values[parent_edge[vertex]]
                );
            } else {
                _prefix[vertex] = Group::op(
                    _prefix[_parent[vertex]],
                    values[vertex]
                );
            }
        }
    }

    int size() const {
        return _n;
    }

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

    int root() const {
        return _root;
    }

    int lca(int first, int second) const {
        check_vertex(first);
        check_vertex(second);
        while (_head[first] != _head[second]) {
            if (_depth[_head[first]] < _depth[_head[second]]) {
                std::swap(first, second);
            }
            first = _parent[_head[first]];
        }
        return _depth[first] < _depth[second] ? first : second;
    }

    // Product on the root-to-vertex path. The root vertex is included for
    // vertex values; no edge lies above it in edge-value mode.
    value_type prod(int vertex) const {
        check_vertex(vertex);
        return _prefix[vertex];
    }

    // Product on the simple path from first to second. Both endpoints are
    // included for vertex values.
    value_type prod(int first, int second) const {
        int ancestor = lca(first, second);
        value_type result = Group::op(_prefix[first], _prefix[second]);
        result = Group::op(result, Group::inv(_prefix[ancestor]));
        if constexpr (EdgeValues) {
            result = Group::op(result, Group::inv(_prefix[ancestor]));
        } else if (_parent[ancestor] != -1) {
            result = Group::op(
                result,
                Group::inv(_prefix[_parent[ancestor]])
            );
        }
        return result;
    }
};

template <m1une::monoid::IsCommutativeGroup Group>
using TreeEdgeCumulativeProduct = TreeCumulativeProduct<Group, true>;

template <class T, bool EdgeValues = false>
class TreeCumulativeSum
    : public TreeCumulativeProduct<m1une::monoid::Add<T>, EdgeValues> {
   private:
    using Base =
        TreeCumulativeProduct<m1une::monoid::Add<T>, EdgeValues>;

   public:
    using Base::Base;

    T sum(int vertex) const {
        return Base::prod(vertex);
    }

    T sum(int first, int second) const {
        return Base::prod(first, second);
    }
};

template <class T>
using TreeEdgeCumulativeSum = TreeCumulativeSum<T, true>;

}  // namespace tree
}  // namespace m1une

#endif  // M1UNE_TREE_CUMULATIVE_SUM_HPP

#line 1 "graph/tree/cumulative_sum.hpp"



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

#line 1 "monoid/add.hpp"



namespace m1une {
namespace monoid {

// Monoid for addition (Range Sum).
template <typename T>
struct Add {
    using value_type = T;
    static constexpr bool commutative = true;

    // Returns the identity element for addition, which is 0.
    static constexpr T id() {
        return T(0);
    }

    // Returns the sum of a and b.
    static constexpr T op(const T& a, const T& b) {
        return a + b;
    }

    static constexpr T inv(const T& x) {
        return -x;
    }
};

}  // namespace monoid
}  // namespace m1une


#line 1 "monoid/concept.hpp"



#include <concepts>

namespace m1une {
namespace monoid {

// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
    // 1. Must define `value_type`
    typename M::value_type;

    // 2. Must have a static method `id()` returning `value_type`
    { M::id() } -> std::same_as<typename M::value_type>;

    // 3. Must have a static method `op(a, b)` returning `value_type`
    { M::op(a, b) } -> std::same_as<typename M::value_type>;
};

// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
    { M::inv(a) } -> std::same_as<typename M::value_type>;
};

// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;

}  // namespace monoid
}  // namespace m1une


#line 1 "graph/graph.hpp"



#include <array>
#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 12 "graph/tree/cumulative_sum.hpp"

namespace m1une {
namespace tree {

// Static cumulative products on root paths. Values are attached to vertices by
// default; set EdgeValues to true to index them by graph edge id instead.
template <m1une::monoid::IsCommutativeGroup Group, bool EdgeValues = false>
class TreeCumulativeProduct {
   public:
    using value_type = typename Group::value_type;

   private:
    int _n = 0;
    int _root = -1;
    std::vector<int> _parent;
    std::vector<int> _depth;
    std::vector<int> _head;
    std::vector<value_type> _prefix;

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

   public:
    TreeCumulativeProduct() = default;

    template <class EdgeCost>
    explicit TreeCumulativeProduct(
        const m1une::graph::Graph<EdgeCost>& graph,
        const std::vector<value_type>& values,
        int root = 0
    ) {
        build(graph, values, root);
    }

    template <class EdgeCost>
    void build(
        const m1une::graph::Graph<EdgeCost>& graph,
        const std::vector<value_type>& values,
        int root = 0
    ) {
        _n = graph.size();
        _root = _n == 0 ? -1 : root;
        assert(
            int(values.size())
            == (EdgeValues ? graph.edge_count() : graph.size())
        );

        _parent.assign(_n, -2);
        _depth.assign(_n, 0);
        _head.assign(_n, -1);
        _prefix.assign(_n, Group::id());
        if (_n == 0) return;
        assert(0 <= root && root < _n);

        std::vector<int> parent_edge(_n, -1);
        std::vector<int> order;
        order.reserve(_n);
        std::vector<int> stack = {root};
        _parent[root] = -1;
        while (!stack.empty()) {
            int vertex = stack.back();
            stack.pop_back();
            order.push_back(vertex);
            for (const auto& edge : graph[vertex]) {
                if (!edge.alive || _parent[edge.to] != -2) continue;
                _parent[edge.to] = vertex;
                parent_edge[edge.to] = edge.id;
                _depth[edge.to] = _depth[vertex] + 1;
                stack.push_back(edge.to);
            }
        }
        assert(int(order.size()) == _n);

        std::vector<int> subtree_size(_n, 1);
        std::vector<int> heavy(_n, -1);
        for (int index = _n - 1; index > 0; index--) {
            int vertex = order[index];
            int parent = _parent[vertex];
            subtree_size[parent] += subtree_size[vertex];
            if (
                heavy[parent] == -1
                || subtree_size[heavy[parent]] < subtree_size[vertex]
            ) {
                heavy[parent] = vertex;
            }
        }

        std::vector<std::pair<int, int>> starts;
        starts.emplace_back(root, root);
        while (!starts.empty()) {
            auto [start, head] = starts.back();
            starts.pop_back();
            for (
                int vertex = start;
                vertex != -1;
                vertex = heavy[vertex]
            ) {
                _head[vertex] = head;
                for (const auto& edge : graph[vertex]) {
                    if (
                        edge.alive && _parent[edge.to] == vertex
                        && edge.to != heavy[vertex]
                    ) {
                        starts.emplace_back(edge.to, edge.to);
                    }
                }
            }
        }

        if constexpr (!EdgeValues) _prefix[root] = values[root];
        for (int vertex : order) {
            if (vertex == root) continue;
            if constexpr (EdgeValues) {
                assert(0 <= parent_edge[vertex]);
                _prefix[vertex] = Group::op(
                    _prefix[_parent[vertex]],
                    values[parent_edge[vertex]]
                );
            } else {
                _prefix[vertex] = Group::op(
                    _prefix[_parent[vertex]],
                    values[vertex]
                );
            }
        }
    }

    int size() const {
        return _n;
    }

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

    int root() const {
        return _root;
    }

    int lca(int first, int second) const {
        check_vertex(first);
        check_vertex(second);
        while (_head[first] != _head[second]) {
            if (_depth[_head[first]] < _depth[_head[second]]) {
                std::swap(first, second);
            }
            first = _parent[_head[first]];
        }
        return _depth[first] < _depth[second] ? first : second;
    }

    // Product on the root-to-vertex path. The root vertex is included for
    // vertex values; no edge lies above it in edge-value mode.
    value_type prod(int vertex) const {
        check_vertex(vertex);
        return _prefix[vertex];
    }

    // Product on the simple path from first to second. Both endpoints are
    // included for vertex values.
    value_type prod(int first, int second) const {
        int ancestor = lca(first, second);
        value_type result = Group::op(_prefix[first], _prefix[second]);
        result = Group::op(result, Group::inv(_prefix[ancestor]));
        if constexpr (EdgeValues) {
            result = Group::op(result, Group::inv(_prefix[ancestor]));
        } else if (_parent[ancestor] != -1) {
            result = Group::op(
                result,
                Group::inv(_prefix[_parent[ancestor]])
            );
        }
        return result;
    }
};

template <m1une::monoid::IsCommutativeGroup Group>
using TreeEdgeCumulativeProduct = TreeCumulativeProduct<Group, true>;

template <class T, bool EdgeValues = false>
class TreeCumulativeSum
    : public TreeCumulativeProduct<m1une::monoid::Add<T>, EdgeValues> {
   private:
    using Base =
        TreeCumulativeProduct<m1une::monoid::Add<T>, EdgeValues>;

   public:
    using Base::Base;

    T sum(int vertex) const {
        return Base::prod(vertex);
    }

    T sum(int first, int second) const {
        return Base::prod(first, second);
    }
};

template <class T>
using TreeEdgeCumulativeSum = TreeCumulativeSum<T, true>;

}  // namespace tree
}  // namespace m1une

m1une's library

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

Tree Cumulative Sum
(graph/tree/cumulative_sum.hpp)

Overview

Requirements and Behavior

Types

Interface

Example

Depends on

Required by

Verified with

Code

Tree Cumulative Sum (graph/tree/cumulative_sum.hpp)

Overview

Requirements and Behavior

Types

Interface

Example

Depends on

Required by

Verified with

Code

Tree Cumulative Sum
(graph/tree/cumulative_sum.hpp)