Segment Tree (only query is implemented)

segtree.hh

#include <limits>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdint>

#if __cplusplus >= 201703
#define IF_CONSTEXPR if constexpr
#else
#define IF_CONSTEXPR if
#endif

template<class T>
using should_move = std::is_same<T, std::remove_reference_t<T>>; // same trick as std::forward does

template<class T>
T&& forward_subpart(T&& value, std::true_type whether_should_move) {
  return std::move(value);
}

template<class T>
T&& forward_subpart(T&& value, std::false_type whether_should_move) {
  return value;
}

uint64_t msb64(uint64_t x) {
  x |= (x >> 1);
  x |= (x >> 2);
  x |= (x >> 4);
  x |= (x >> 8);
  x |= (x >> 16);
  x |= (x >> 32);
  return x & ~(x >> 1);
}

template<class Monoid>
struct SegmentTree {
  // This layout is intentional:
  // we need the constants to be initialized when constructing store,
  // at the same time the overhead incurred by such layout is expected to be
  // order of magnitude less than the overall footprint in typical usage.

  const size_t lowest_layer_idx;
  const size_t lowest_layer_begin;
  std::vector<Monoid> store;

  template<class Cont>
  SegmentTree(Cont&& cont)
    : lowest_layer_idx(std::ceil(std::log2(cont.size())))
    , lowest_layer_begin(1 << lowest_layer_idx) // derived from the formula of geometric progression sum; vertexes numbered from 1
    , store(lowest_layer_begin << 1) {
    IF_CONSTEXPR (should_move<Cont>::value) {
      std::move(std::begin(cont), std::end(cont), store.begin() + lowest_layer_begin);
    } else {
      std::copy(std::begin(cont), std::end(cont), store.begin() + lowest_layer_begin);
    }
    for (int idx = lowest_layer_begin - 1; idx > 0; --idx) {
      store[idx] = Monoid::combine(store[2 * idx], store[2 * idx + 1]);
    }
  }

  Monoid query(size_t left, size_t right) { // 1-based numeration, half-open range
    if (left < 1 || left >= right || right > lowest_layer_begin * 2) { return Monoid{}; };
    left -= 1, right -= 1;
    Monoid result;
    size_t span;
    for (uint64_t subsegment_begin = left; subsegment_begin < right; subsegment_begin += span) {
      size_t max_possible_span = (subsegment_begin ? subsegment_begin & -subsegment_begin : std::numeric_limits<size_t>::max());
      size_t max_allowed_span = msb64(right - subsegment_begin);
      span = std::min(max_possible_span, max_allowed_span);

      result = Monoid::combine(result, store[(lowest_layer_begin + subsegment_begin) / span]);
    }
    return result;
  }
};

test.cc

#include <iostream>

#include "segtree.hh"

template<class Derived>
struct Monoid {
  template<class U, class V, class = typename std::enable_if<std::is_same<std::decay_t<U>, Derived>::value && std::is_same<std::decay_t<V>, Derived>::value>>
  static Derived combine(U&& a, V&& b) {
    return Derived{Derived::comb(forward_subpart(a.value, should_move<U>{}), forward_subpart(b.value, should_move<V>{}))};
  }
};

template<class T, class = typename std::enable_if<std::is_integral<T>::value, void>::type>
struct MonoidMax : Monoid<MonoidMax<T>> {
  T value = std::numeric_limits<T>::min();
  static constexpr const T&(*comb)(const T&, const T&) = std::max<T>;

  MonoidMax() {}
  MonoidMax(T a) : value(a) {};
};

int main() {
  int n; std::cin >> n;
  std::vector<int> a(n); for (auto& x : a) std::cin >> x;
  int m; std::cin >> m;

  SegmentTree<MonoidMax<int64_t>> segtree(std::move(a));

  for (int i = 0; i <= n - m; ++i) {
    std::cout << segtree.query(i + 1, i + 1 + m).value << " ";
  }
}