offline_dynamic_component_sum.hpp

SECTIONGraph INCLUDEnoya/offline_dynamic_component_sum.hpp

Offline fully dynamic undirected connectivity with additive vertex values and component-sum queries. Every edge and every vertex increment is placed on the segment-tree nodes covering the time interval where it is active. A depth-first traversal applies those operations to a union-find whose parent links and component sums can both be rolled back, so each leaf sees exactly the graph and values at that query time.

Verified by dynamic_graph_vertex_add_component_sum.

离线处理动态加删边、点权修改与连通块权值和查询；适合图随时间变化的分量统计。

Implementation

View on GitHub

SourceExpanded

#ifndef NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP
#define NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP 1

/// @complexity Time: O(Q log Q log V) for Q operations on V vertices.
/// Space: O(Q log Q + V).

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

namespace noya {

/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Every edge and every vertex increment is
/// placed on the segment-tree nodes covering the time interval where it is
/// active. A depth-first traversal applies those operations to a union-find
/// whose parent links and component sums can both be rolled back, so each leaf
/// sees exactly the graph and values at that query time.
template <class T> struct offline_dynamic_component_sum {
  enum class event_type { add_edge, remove_edge, add_value, query_sum };

  struct event {
    event_type type;
    int first;
    int second = -1;
    T value{};
    int query_id = -1;
  };

  std::vector<T> initial_values;
  std::vector<event> events;
  int query_count = 0;

  offline_dynamic_component_sum() = default;
  explicit offline_dynamic_component_sum(std::vector<T> values)
      : initial_values(std::move(values)) {}

  /// @brief Record the insertion of one copy of an undirected edge.
  void add_edge(int first, int second) {
    check_vertex(first);
    check_vertex(second);
    normalize(first, second);
    events.push_back({event_type::add_edge, first, second});
  }

  /// @brief Record the removal of the most recently inserted active copy.
  void remove_edge(int first, int second) {
    check_vertex(first);
    check_vertex(second);
    normalize(first, second);
    events.push_back({event_type::remove_edge, first, second});
  }

  /// @brief Add delta to one vertex from this time onward.
  void add_vertex(int vertex, const T &delta) {
    check_vertex(vertex);
    events.push_back({event_type::add_value, vertex, -1, delta});
  }

  /// @brief Record a component-sum query and return its answer index.
  int add_query(int vertex) {
    check_vertex(vertex);
    int id = query_count++;
    events.push_back({event_type::query_sum, vertex, -1, T{}, id});
    return id;
  }

  /// @brief Solve all recorded component-sum queries.
  std::vector<T> solve() const {
    int time_count = int(events.size());
    if (time_count == 0) {
      return std::vector<T>(query_count);
    }
    std::vector<std::vector<std::pair<int, int>>> edge_tree(4 * time_count);
    std::vector<std::vector<std::pair<int, T>>> addition_tree(4 * time_count);

    auto add_edge_interval = [&](auto &self, int node, int left, int right,
                                 int query_left, int query_right,
                                 std::pair<int, int> edge) -> void {
      if (query_right <= left || right <= query_left) {
        return;
      }
      if (query_left <= left && right <= query_right) {
        edge_tree[node].push_back(edge);
        return;
      }
      int middle = (left + right) / 2;
      self(self, node * 2, left, middle, query_left, query_right, edge);
      self(self, node * 2 + 1, middle, right, query_left, query_right, edge);
    };
    auto add_value_interval = [&](auto &self, int node, int left, int right,
                                  int query_left, int vertex,
                                  const T &delta) -> void {
      if (right <= query_left) {
        return;
      }
      if (query_left <= left) {
        addition_tree[node].emplace_back(vertex, delta);
        return;
      }
      int middle = (left + right) / 2;
      self(self, node * 2, left, middle, query_left, vertex, delta);
      self(self, node * 2 + 1, middle, right, query_left, vertex, delta);
    };

    std::map<std::pair<int, int>, std::vector<int>> active_edges;
    for (int time = 0; time < time_count; time++) {
      const event &current = events[time];
      std::pair<int, int> edge = {current.first, current.second};
      if (current.type == event_type::add_edge) {
        active_edges[edge].push_back(time);
      } else if (current.type == event_type::remove_edge) {
        auto iterator = active_edges.find(edge);
        assert(iterator != active_edges.end() && !iterator->second.empty());
        if (iterator == active_edges.end() || iterator->second.empty()) {
          continue;
        }
        int start = iterator->second.back();
        iterator->second.pop_back();
        add_edge_interval(add_edge_interval, 1, 0, time_count, start, time,
                          edge);
      } else if (current.type == event_type::add_value) {
        add_value_interval(add_value_interval, 1, 0, time_count, time,
                           current.first, current.value);
      }
    }
    for (const auto &[edge, starts] : active_edges) {
      for (int start : starts) {
        add_edge_interval(add_edge_interval, 1, 0, time_count, start,
                          time_count, edge);
      }
    }

    rollback_component_dsu dsu(initial_values);
    std::vector<T> answers(query_count);
    auto dfs = [&](auto &self, int node, int left, int right) -> void {
      int state = dsu.snapshot();
      for (auto [first, second] : edge_tree[node]) {
        dsu.merge(first, second);
      }
      for (const auto &[vertex, delta] : addition_tree[node]) {
        dsu.add_vertex(vertex, delta);
      }
      if (right - left == 1) {
        const event &current = events[left];
        if (current.type == event_type::query_sum) {
          answers[current.query_id] = dsu.component_sum(current.first);
        }
      } else {
        int middle = (left + right) / 2;
        self(self, node * 2, left, middle);
        self(self, node * 2 + 1, middle, right);
      }
      dsu.rollback(state);
    };
    dfs(dfs, 1, 0, time_count);
    return answers;
  }

private:
  struct rollback_component_dsu {
    struct change {
      int kind;
      int first;
      int first_parent;
      int second;
      int second_parent;
      T previous_sum;
    };

    std::vector<int> parent_or_size;
    std::vector<T> sums;
    std::vector<change> history;

    explicit rollback_component_dsu(const std::vector<T> &values)
        : parent_or_size(values.size(), -1), sums(values) {}

    int leader(int vertex) const {
      while (parent_or_size[vertex] >= 0) {
        vertex = parent_or_size[vertex];
      }
      return vertex;
    }

    void merge(int first, int second) {
      first = leader(first);
      second = leader(second);
      if (first == second) {
        history.push_back({0, -1, 0, -1, 0, T{}});
        return;
      }
      if (-parent_or_size[first] < -parent_or_size[second]) {
        std::swap(first, second);
      }
      history.push_back({1, first, parent_or_size[first], second,
                         parent_or_size[second], sums[first]});
      parent_or_size[first] += parent_or_size[second];
      parent_or_size[second] = first;
      sums[first] += sums[second];
    }

    void add_vertex(int vertex, const T &delta) {
      int root = leader(vertex);
      history.push_back({2, root, 0, -1, 0, sums[root]});
      sums[root] += delta;
    }

    T component_sum(int vertex) const { return sums[leader(vertex)]; }

    int snapshot() const { return int(history.size()); }

    void rollback(int state) {
      while (int(history.size()) > state) {
        change last = std::move(history.back());
        history.pop_back();
        if (last.kind == 1) {
          parent_or_size[last.first] = last.first_parent;
          parent_or_size[last.second] = last.second_parent;
          sums[last.first] = std::move(last.previous_sum);
        } else if (last.kind == 2) {
          sums[last.first] = std::move(last.previous_sum);
        }
      }
    }
  };

  void check_vertex(int vertex) const {
    assert(0 <= vertex && vertex < int(initial_values.size()));
  }

  static void normalize(int &first, int &second) {
    if (first > second) {
      std::swap(first, second);
    }
  }
};

} // namespace noya

#endif // NOYA_OFFLINE_DYNAMIC_COMPONENT_SUM_HPP

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

/// @complexity Time: O(Q log Q log V) for Q operations on V vertices.
/// Space: O(Q log Q + V).

namespace noya {

/// @brief Offline fully dynamic undirected connectivity with additive vertex
/// values and component-sum queries. Every edge and every vertex increment is
/// placed on the segment-tree nodes covering the time interval where it is
/// active. A depth-first traversal applies those operations to a union-find
/// whose parent links and component sums can both be rolled back, so each leaf
/// sees exactly the graph and values at that query time.
template <class T> struct offline_dynamic_component_sum {
  enum class event_type { add_edge, remove_edge, add_value, query_sum };

  struct event {
    event_type type;
    int first;
    int second = -1;
    T value{};
    int query_id = -1;
  };

  std::vector<T> initial_values;
  std::vector<event> events;
  int query_count = 0;

  offline_dynamic_component_sum() = default;
  explicit offline_dynamic_component_sum(std::vector<T> values)
      : initial_values(std::move(values)) {}

  /// @brief Record the insertion of one copy of an undirected edge.
  void add_edge(int first, int second) {
    check_vertex(first);
    check_vertex(second);
    normalize(first, second);
    events.push_back({event_type::add_edge, first, second});
  }

  /// @brief Record the removal of the most recently inserted active copy.
  void remove_edge(int first, int second) {
    check_vertex(first);
    check_vertex(second);
    normalize(first, second);
    events.push_back({event_type::remove_edge, first, second});
  }

  /// @brief Add delta to one vertex from this time onward.
  void add_vertex(int vertex, const T &delta) {
    check_vertex(vertex);
    events.push_back({event_type::add_value, vertex, -1, delta});
  }

  /// @brief Record a component-sum query and return its answer index.
  int add_query(int vertex) {
    check_vertex(vertex);
    int id = query_count++;
    events.push_back({event_type::query_sum, vertex, -1, T{}, id});
    return id;
  }

  /// @brief Solve all recorded component-sum queries.
  std::vector<T> solve() const {
    int time_count = int(events.size());
    if (time_count == 0) {
      return std::vector<T>(query_count);
    }
    std::vector<std::vector<std::pair<int, int>>> edge_tree(4 * time_count);
    std::vector<std::vector<std::pair<int, T>>> addition_tree(4 * time_count);

    auto add_edge_interval = [&](auto &self, int node, int left, int right,
                                 int query_left, int query_right,
                                 std::pair<int, int> edge) -> void {
      if (query_right <= left || right <= query_left) {
        return;
      }
      if (query_left <= left && right <= query_right) {
        edge_tree[node].push_back(edge);
        return;
      }
      int middle = (left + right) / 2;
      self(self, node * 2, left, middle, query_left, query_right, edge);
      self(self, node * 2 + 1, middle, right, query_left, query_right, edge);
    };
    auto add_value_interval = [&](auto &self, int node, int left, int right,
                                  int query_left, int vertex,
                                  const T &delta) -> void {
      if (right <= query_left) {
        return;
      }
      if (query_left <= left) {
        addition_tree[node].emplace_back(vertex, delta);
        return;
      }
      int middle = (left + right) / 2;
      self(self, node * 2, left, middle, query_left, vertex, delta);
      self(self, node * 2 + 1, middle, right, query_left, vertex, delta);
    };

    std::map<std::pair<int, int>, std::vector<int>> active_edges;
    for (int time = 0; time < time_count; time++) {
      const event &current = events[time];
      std::pair<int, int> edge = {current.first, current.second};
      if (current.type == event_type::add_edge) {
        active_edges[edge].push_back(time);
      } else if (current.type == event_type::remove_edge) {
        auto iterator = active_edges.find(edge);
        assert(iterator != active_edges.end() && !iterator->second.empty());
        if (iterator == active_edges.end() || iterator->second.empty()) {
          continue;
        }
        int start = iterator->second.back();
        iterator->second.pop_back();
        add_edge_interval(add_edge_interval, 1, 0, time_count, start, time,
                          edge);
      } else if (current.type == event_type::add_value) {
        add_value_interval(add_value_interval, 1, 0, time_count, time,
                           current.first, current.value);
      }
    }
    for (const auto &[edge, starts] : active_edges) {
      for (int start : starts) {
        add_edge_interval(add_edge_interval, 1, 0, time_count, start,
                          time_count, edge);
      }
    }

    rollback_component_dsu dsu(initial_values);
    std::vector<T> answers(query_count);
    auto dfs = [&](auto &self, int node, int left, int right) -> void {
      int state = dsu.snapshot();
      for (auto [first, second] : edge_tree[node]) {
        dsu.merge(first, second);
      }
      for (const auto &[vertex, delta] : addition_tree[node]) {
        dsu.add_vertex(vertex, delta);
      }
      if (right - left == 1) {
        const event &current = events[left];
        if (current.type == event_type::query_sum) {
          answers[current.query_id] = dsu.component_sum(current.first);
        }
      } else {
        int middle = (left + right) / 2;
        self(self, node * 2, left, middle);
        self(self, node * 2 + 1, middle, right);
      }
      dsu.rollback(state);
    };
    dfs(dfs, 1, 0, time_count);
    return answers;
  }

private:
  struct rollback_component_dsu {
    struct change {
      int kind;
      int first;
      int first_parent;
      int second;
      int second_parent;
      T previous_sum;
    };

    std::vector<int> parent_or_size;
    std::vector<T> sums;
    std::vector<change> history;

    explicit rollback_component_dsu(const std::vector<T> &values)
        : parent_or_size(values.size(), -1), sums(values) {}

    int leader(int vertex) const {
      while (parent_or_size[vertex] >= 0) {
        vertex = parent_or_size[vertex];
      }
      return vertex;
    }

    void merge(int first, int second) {
      first = leader(first);
      second = leader(second);
      if (first == second) {
        history.push_back({0, -1, 0, -1, 0, T{}});
        return;
      }
      if (-parent_or_size[first] < -parent_or_size[second]) {
        std::swap(first, second);
      }
      history.push_back({1, first, parent_or_size[first], second,
                         parent_or_size[second], sums[first]});
      parent_or_size[first] += parent_or_size[second];
      parent_or_size[second] = first;
      sums[first] += sums[second];
    }

    void add_vertex(int vertex, const T &delta) {
      int root = leader(vertex);
      history.push_back({2, root, 0, -1, 0, sums[root]});
      sums[root] += delta;
    }

    T component_sum(int vertex) const { return sums[leader(vertex)]; }

    int snapshot() const { return int(history.size()); }

    void rollback(int state) {
      while (int(history.size()) > state) {
        change last = std::move(history.back());
        history.pop_back();
        if (last.kind == 1) {
          parent_or_size[last.first] = last.first_parent;
          parent_or_size[last.second] = last.second_parent;
          sums[last.first] = std::move(last.previous_sum);
        } else if (last.kind == 2) {
          sums[last.first] = std::move(last.previous_sum);
        }
      }
    }
  };

  void check_vertex(int vertex) const {
    assert(0 <= vertex && vertex < int(initial_values.size()));
  }

  static void normalize(int &first, int &second) {
    if (first > second) {
      std::swap(first, second);
    }
  }
};

} // namespace noya