Too much templates for today...

segment_tree.cpp

#include <vector>
#include <functional>

#include <iostream>


using std::vector;

template<typename T = int, template <typename> class Combiner = std::plus>
class SegmentTree {
    vector<T> tree;
    std::function<T(T, T)> combine;
    
    size_t size() const {
        return tree.size() / 4;
    }

    int left(int i) {
        return 2 * i + 1;
    }

    int right(int i) {
        return 2 * i + 2;
    }

    template<template <typename> class RandomAccessContainer>
    void build(int l, int r, int i, RandomAccessContainer<T> const& a) {
        if (l == r) { tree[i] = a[l]; return; }
        int mid = (l + r) / 2;
        build(l, mid, left(i), a);
        build(mid + 1, r, right(i), a);
        tree[i] = combine(tree[left(i)], tree[right(i)]);
    }

    void update(int index, T value, int l, int r, int i) {
        if (l == r) { tree[i] = value; return; }
        int mid = (l + r) / 2;
        if (index <= mid) update(index, value, l, mid, left(i));
        else update(index, value, mid + 1, r, right(i));
        tree[i] = combine(tree[left(i)], tree[right(i)]);
    }

    int query(T value, int l, int r, int i) {
        if (l > r) return -1;
        if (l == r) return l;
        T left_value = tree[left(i)];
        int mid = (l + r) / 2;
        if (left_value >= value) return query(value, l, mid, left(i));
        return query(value - left_value, mid + 1, r, right(i));
    }

    public:

        template<template <typename> class RandomAccessContainer>
        SegmentTree(int n, RandomAccessContainer<T> const& a)
        : tree(4 * n), combine(Combiner<T>()) {
            build(0, n - 1, 0, a);
        }

        void update(int index, T value) {
            update(index, value, 0, size() - 1, 0);
        }

        int query(T value) {
            return query(value, 0, size() - 1, 0);
        }
};

template<typename T>
struct ConstantContainer {
    T value;
    ConstantContainer(T const& value): value(value) {}
    T const& operator[](int) const {
        return value;
    }
};

int main() {
    int n = 6;
    ConstantContainer<int> ones(1);
    SegmentTree<> tree(n, ones);
    for (int i: {1, 2, 3, 4, 5}) {
        std::cout << tree.query(i) << " ";
        tree.update(i, 0);
    }
    std::cout << std::endl;
    return 0;
}