Second-order difference array (tools/second_order_imos.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-01-31 15:30:47+09:00
• Include: #include "tools/second_order_imos.hpp"

It is an array with an auxiliary second-order difference array for executing queries that add arithmetic sequences.

License

• CC0

Author

• anqooqie

Constructor

template <tools::non_bool_integral T>
second_order_imos<T> a(int n = 0);

It creates an array of type T and length $n$ filled with $0$. You can get $a_i$ in the order $i = 0, 1, \ldots, {n - 1}$. Once $a_i$ is got, it is fixed and cannot be updated thereafter.

Constraints

• $n \geq 0$

Time Complexity

• $O(n)$

size

int a.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

operator[]

const T& a.operator[](int i);

It returns the const reference to $a_i$.

Constraints

• $0 \leq i < n$

Time Complexity

• $O(1)$ amortized

add

void a.add(int l, int r, T x, T d);

It performs a query that $a_i \leftarrow a_i + x + (i - l) d$ for each $i$ such that $l \leq i < r$.

Constraints

• $0 \leq l \leq r \leq n$
• $i^\ast < l$ where $i^\ast$ is the largest $i$ in a[i] called so far or $-1$ (if you have not called it so far).

Time Complexity

• $O(1)$

Depends on

• Concept for integral types including tools::int128_t and tools::uint128_t (tools/integral.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• tools::integral except for bool (tools/non_bool_integral.hpp)

Verified with

• tests/cartesian_tree/tree_based_interval.test.cpp
• tests/second_order_imos.test.cpp

Code

#ifndef TOOLS_SECOND_ORDER_IMOS_HPP
#define TOOLS_SECOND_ORDER_IMOS_HPP

#include <cassert>
#include <compare>
#include <cstddef>
#include <iterator>
#include <vector>
#include "tools/non_bool_integral.hpp"

namespace tools {
  template <tools::non_bool_integral T>
  class second_order_imos {
    std::vector<T> m_vector;
    std::vector<T> m_diffs2;
    int m_processed;

  public:
    class iterator {
      second_order_imos<T> *m_parent;
      std::size_t m_i;

    public:
      using reference = const T&;
      using value_type = T;
      using difference_type = std::ptrdiff_t;
      using pointer = const T*;
      using iterator_category = std::random_access_iterator_tag;

      iterator() = default;
      iterator(second_order_imos<T> * const parent, const std::size_t i) : m_parent(parent), m_i(i) {
      }

      reference operator*() const {
        return (*this->m_parent)[this->m_i];
      }
      pointer operator->() const {
        return &(*(*this));
      }

      iterator& operator++() {
        ++this->m_i;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_i;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_i += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_i -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend std::strong_ordering operator<=>(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i <=> rhs.m_i;
      }
      friend bool operator==(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i == rhs.m_i;
      }
    };

    second_order_imos() : second_order_imos(0) {
    }
    second_order_imos(const int n) : m_vector(n, 0), m_diffs2(n + 2, 0), m_processed(0) {
    }

    int size() const {
      return this->m_vector.size();
    }
    const T& operator[](const int i) {
      assert(0 <= i && i < this->size());
      auto& j = this->m_processed;
      do {
        if (i < j) break;
        if (j == 0) {
          this->m_vector[j] = this->m_diffs2[j];
          ++j;
          if (i < j) break;
        }
        if (j == 1) {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1];
          ++j;
          if (i < j) break;
        }
        do {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1] - this->m_vector[j - 2];
          ++j;
        } while (j <= i);
      } while (false);
      return this->m_vector[i];
    }

    iterator begin() { return iterator(this, 0); }
    iterator end() { return iterator(this, this->size()); }
    std::reverse_iterator<iterator> rbegin() { return std::make_reverse_iterator(this->end()); }
    std::reverse_iterator<iterator> rend() { return std::make_reverse_iterator(this->begin()); }

    void add(const int l, const int r, const T a, const T d) {
      assert(0 <= l && l <= r && r <= this->size());
      assert(this->m_processed <= l);
      this->m_diffs2[l] += a;
      this->m_diffs2[l + 1] += d - a;
      this->m_diffs2[r] -= a + (r - l) * d;
      this->m_diffs2[r + 1] += a + (r - l - 1) * d;
    }
  };
}

#endif

#line 1 "tools/second_order_imos.hpp"



#include <cassert>
#include <compare>
#include <cstddef>
#include <iterator>
#include <vector>
#line 1 "tools/non_bool_integral.hpp"



#include <concepts>
#include <type_traits>
#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 7 "tools/non_bool_integral.hpp"

namespace tools {
  template <typename T>
  concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}


#line 10 "tools/second_order_imos.hpp"

namespace tools {
  template <tools::non_bool_integral T>
  class second_order_imos {
    std::vector<T> m_vector;
    std::vector<T> m_diffs2;
    int m_processed;

  public:
    class iterator {
      second_order_imos<T> *m_parent;
      std::size_t m_i;

    public:
      using reference = const T&;
      using value_type = T;
      using difference_type = std::ptrdiff_t;
      using pointer = const T*;
      using iterator_category = std::random_access_iterator_tag;

      iterator() = default;
      iterator(second_order_imos<T> * const parent, const std::size_t i) : m_parent(parent), m_i(i) {
      }

      reference operator*() const {
        return (*this->m_parent)[this->m_i];
      }
      pointer operator->() const {
        return &(*(*this));
      }

      iterator& operator++() {
        ++this->m_i;
        return *this;
      }
      iterator operator++(int) {
        const auto self = *this;
        ++*this;
        return self;
      }
      iterator& operator--() {
        --this->m_i;
        return *this;
      }
      iterator operator--(int) {
        const auto self = *this;
        --*this;
        return self;
      }
      iterator& operator+=(const difference_type n) {
        this->m_i += n;
        return *this;
      }
      iterator& operator-=(const difference_type n) {
        this->m_i -= n;
        return *this;
      }
      friend iterator operator+(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i + n);
      }
      friend iterator operator+(const difference_type n, const iterator self) {
        return self + n;
      }
      friend iterator operator-(const iterator self, const difference_type n) {
        return iterator(self.m_parent, self.m_i - n);
      }
      friend difference_type operator-(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return static_cast<difference_type>(lhs.m_i) - static_cast<difference_type>(rhs.m_i);
      }
      reference operator[](const difference_type n) const {
        return *(*this + n);
      }

      friend std::strong_ordering operator<=>(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i <=> rhs.m_i;
      }
      friend bool operator==(const iterator lhs, const iterator rhs) {
        assert(lhs.m_parent == rhs.m_parent);
        return lhs.m_i == rhs.m_i;
      }
    };

    second_order_imos() : second_order_imos(0) {
    }
    second_order_imos(const int n) : m_vector(n, 0), m_diffs2(n + 2, 0), m_processed(0) {
    }

    int size() const {
      return this->m_vector.size();
    }
    const T& operator[](const int i) {
      assert(0 <= i && i < this->size());
      auto& j = this->m_processed;
      do {
        if (i < j) break;
        if (j == 0) {
          this->m_vector[j] = this->m_diffs2[j];
          ++j;
          if (i < j) break;
        }
        if (j == 1) {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1];
          ++j;
          if (i < j) break;
        }
        do {
          this->m_vector[j] = this->m_diffs2[j] + 2 * this->m_vector[j - 1] - this->m_vector[j - 2];
          ++j;
        } while (j <= i);
      } while (false);
      return this->m_vector[i];
    }

    iterator begin() { return iterator(this, 0); }
    iterator end() { return iterator(this, this->size()); }
    std::reverse_iterator<iterator> rbegin() { return std::make_reverse_iterator(this->end()); }
    std::reverse_iterator<iterator> rend() { return std::make_reverse_iterator(this->begin()); }

    void add(const int l, const int r, const T a, const T d) {
      assert(0 <= l && l <= r && r <= this->size());
      assert(this->m_processed <= l);
      this->m_diffs2[l] += a;
      this->m_diffs2[l + 1] += d - a;
      this->m_diffs2[r] -= a + (r - l) * d;
      this->m_diffs2[r + 1] += a + (r - l - 1) * d;
    }
  };
}

Back to top page