range_set_range_product.hpp

SECTIONData Structure INCLUDEnoya/range_set_range_product.hpp

Segment tree for assigning one value to a range and taking an ordered monoid product. For every assigned value, powers for all segment lengths are cached in a circular table. Lazy nodes refer to those cached powers, so a full-cover assignment is constant time and no idempotence or commutativity is required from the monoid.

Verified by range_set_range_composite.

支持区间赋成同一个值，并查询区间上的非交换乘积；适合矩阵或函数复合等有顺序的聚合。

Implementation

View on GitHub

SourceExpanded

#ifndef NOYA_RANGE_SET_RANGE_PRODUCT_HPP
#define NOYA_RANGE_SET_RANGE_PRODUCT_HPP 1

/// @complexity Time: O(n) construction and O(log n) per range assignment or
/// ordered range product.
/// Space: O(n).

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

namespace noya {

/// @brief Segment tree for assigning one value to a range and taking an
/// ordered monoid product. For every assigned value, powers for all segment
/// lengths are cached in a circular table. Lazy nodes refer to those cached
/// powers, so a full-cover assignment is constant time and no idempotence or
/// commutativity is required from the monoid.
template <class S, auto op, auto e> struct range_set_range_product {
  int n = 0;
  int size = 1;
  int log = 0;
  int table_iterator = 0;
  std::vector<int> lazy;
  std::vector<int> segment_size;
  std::vector<S> power_table;
  std::vector<S> product;

  range_set_range_product() = default;
  explicit range_set_range_product(const std::vector<S> &values) {
    build(values);
  }

  void build(const std::vector<S> &values) {
    n = int(values.size());
    size = 1;
    log = 0;
    while (size < std::max(1, n)) {
      size <<= 1;
      log++;
    }
    table_iterator = 0;
    lazy.assign(size, -1);
    segment_size.assign(size * 2, size);
    for (int node = size - 1; node >= 1; node--) {
      segment_size[node] = segment_size[node << 1] >> 1;
    }
    power_table.assign(size * 2, e());
    product.assign(size * 2, e());
    for (int i = 0; i < n; i++) {
      product[size + i] = values[i];
    }
    for (int node = size - 1; node >= 1; node--) {
      product[node] = op(product[node << 1], product[node << 1 | 1]);
    }
  }

  void assign(int left, int right, S value) {
    assert(0 <= left && left <= right && right <= n);
    if (left == right) {
      return;
    }
    int tag = table_iterator++;
    if (table_iterator == size * 2) {
      table_iterator = 0;
    }
    power_table[index(tag - size)] = value;
    for (int height = 1; height <= log; height++) {
      value = op(value, value);
      power_table[index(tag - (size >> height))] = value;
    }
    assign_rec(left, right, tag, 1, 0, size);
    propagate_path(bit_reverse(tag & (size - 1)));
  }

  S prod(int left, int right) {
    assert(0 <= left && left <= right && right <= n);
    return left == right ? e() : prod_rec(left, right, 1, 0, size);
  }

private:
  int index(int value) const { return value & (size * 2 - 1); }

  int bit_reverse(int value) const {
    int result = 0;
    for (int bit = 0; bit < log; bit++) {
      result = (result << 1) | (value & 1);
      value >>= 1;
    }
    return result;
  }

  void apply(int node, int tag) {
    if (node < size) {
      lazy[node] = tag;
    }
    product[node] = power_table[index(tag - segment_size[node])];
  }

  void push(int node) {
    if (node >= size || lazy[node] == -1) {
      return;
    }
    apply(node << 1, lazy[node]);
    apply(node << 1 | 1, lazy[node]);
    lazy[node] = -1;
  }

  void propagate_path(int position) {
    position += size;
    for (int height = log; height >= 1; height--) {
      push(position >> height);
    }
  }

  void assign_rec(int left, int right, int tag, int node, int low, int high) {
    if (high <= left || right <= low) {
      return;
    }
    if (left <= low && high <= right) {
      apply(node, tag);
      return;
    }
    push(node);
    int middle = (low + high) / 2;
    assign_rec(left, right, tag, node << 1, low, middle);
    assign_rec(left, right, tag, node << 1 | 1, middle, high);
    product[node] = op(product[node << 1], product[node << 1 | 1]);
  }

  S prod_rec(int left, int right, int node, int low, int high) {
    if (left <= low && high <= right) {
      return product[node];
    }
    push(node);
    int middle = (low + high) / 2;
    if (right <= middle) {
      return prod_rec(left, right, node << 1, low, middle);
    }
    if (middle <= left) {
      return prod_rec(left, right, node << 1 | 1, middle, high);
    }
    return op(prod_rec(left, right, node << 1, low, middle),
              prod_rec(left, right, node << 1 | 1, middle, high));
  }
};

} // namespace noya

#endif // NOYA_RANGE_SET_RANGE_PRODUCT_HPP

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

/// @complexity Time: O(n) construction and O(log n) per range assignment or
/// ordered range product.
/// Space: O(n).

namespace noya {

/// @brief Segment tree for assigning one value to a range and taking an
/// ordered monoid product. For every assigned value, powers for all segment
/// lengths are cached in a circular table. Lazy nodes refer to those cached
/// powers, so a full-cover assignment is constant time and no idempotence or
/// commutativity is required from the monoid.
template <class S, auto op, auto e> struct range_set_range_product {
  int n = 0;
  int size = 1;
  int log = 0;
  int table_iterator = 0;
  std::vector<int> lazy;
  std::vector<int> segment_size;
  std::vector<S> power_table;
  std::vector<S> product;

  range_set_range_product() = default;
  explicit range_set_range_product(const std::vector<S> &values) {
    build(values);
  }

  void build(const std::vector<S> &values) {
    n = int(values.size());
    size = 1;
    log = 0;
    while (size < std::max(1, n)) {
      size <<= 1;
      log++;
    }
    table_iterator = 0;
    lazy.assign(size, -1);
    segment_size.assign(size * 2, size);
    for (int node = size - 1; node >= 1; node--) {
      segment_size[node] = segment_size[node << 1] >> 1;
    }
    power_table.assign(size * 2, e());
    product.assign(size * 2, e());
    for (int i = 0; i < n; i++) {
      product[size + i] = values[i];
    }
    for (int node = size - 1; node >= 1; node--) {
      product[node] = op(product[node << 1], product[node << 1 | 1]);
    }
  }

  void assign(int left, int right, S value) {
    assert(0 <= left && left <= right && right <= n);
    if (left == right) {
      return;
    }
    int tag = table_iterator++;
    if (table_iterator == size * 2) {
      table_iterator = 0;
    }
    power_table[index(tag - size)] = value;
    for (int height = 1; height <= log; height++) {
      value = op(value, value);
      power_table[index(tag - (size >> height))] = value;
    }
    assign_rec(left, right, tag, 1, 0, size);
    propagate_path(bit_reverse(tag & (size - 1)));
  }

  S prod(int left, int right) {
    assert(0 <= left && left <= right && right <= n);
    return left == right ? e() : prod_rec(left, right, 1, 0, size);
  }

private:
  int index(int value) const { return value & (size * 2 - 1); }

  int bit_reverse(int value) const {
    int result = 0;
    for (int bit = 0; bit < log; bit++) {
      result = (result << 1) | (value & 1);
      value >>= 1;
    }
    return result;
  }

  void apply(int node, int tag) {
    if (node < size) {
      lazy[node] = tag;
    }
    product[node] = power_table[index(tag - segment_size[node])];
  }

  void push(int node) {
    if (node >= size || lazy[node] == -1) {
      return;
    }
    apply(node << 1, lazy[node]);
    apply(node << 1 | 1, lazy[node]);
    lazy[node] = -1;
  }

  void propagate_path(int position) {
    position += size;
    for (int height = log; height >= 1; height--) {
      push(position >> height);
    }
  }

  void assign_rec(int left, int right, int tag, int node, int low, int high) {
    if (high <= left || right <= low) {
      return;
    }
    if (left <= low && high <= right) {
      apply(node, tag);
      return;
    }
    push(node);
    int middle = (low + high) / 2;
    assign_rec(left, right, tag, node << 1, low, middle);
    assign_rec(left, right, tag, node << 1 | 1, middle, high);
    product[node] = op(product[node << 1], product[node << 1 | 1]);
  }

  S prod_rec(int left, int right, int node, int low, int high) {
    if (left <= low && high <= right) {
      return product[node];
    }
    push(node);
    int middle = (low + high) / 2;
    if (right <= middle) {
      return prod_rec(left, right, node << 1, low, middle);
    }
    if (middle <= left) {
      return prod_rec(left, right, node << 1 | 1, middle, high);
    }
    return op(prod_rec(left, right, node << 1, low, middle),
              prod_rec(left, right, node << 1 | 1, middle, high));
  }
};

} // namespace noya