segment tree

st.d

/** Generic segment tree for monoids.

Segment tree is a data structure which stores Monoid elements x[], the number
of which, n, is fixed on initialization.  Monoid is a set with an associative
binary operation and identity element.  

The constructor has time complexity of O(n), takes n and initialize the tree
with n copies of identitiy, or takes the elements of initial array.

The tree has two operation both of which is done in Theta(lg n) time:
---
tree[i] = v; // changes i-th element to v,
tree[i..j];  // returns reduce!operation of interval [i..j),
tree[];      // alias of tree[0..n],
tree[i];     // read i-th element of the array; O(1) time.
---

*/
struct SegmentTree(Monoid, alias operation, Monoid Identity)
{
    Monoid[] x;
    size_t n;
    this (size_t n)
    {
        this.n = n.toMPT();
        this.x.length = this.n << 1;
        foreach (ref e; x)
            e = Identity;
    }
    this (Monoid[] x)
    {
        n = x.length.toMPT();
        this.x.length = n << 1;
        foreach (i; 0..n)
            this.x[i] = Identity;
        foreach (i; (n + x.length) .. this.x.length)
            this.x[i] = Identity;
        this.x[n .. (n + x.length)] = x[];
        init(n >> 1);
    }
    private void init(in size_t n)
    {
        if (n == 0)
            return;
        foreach (i; 0..n)
            this.x[n + i] = operation(this.x[(n + i) << 1], this.x[(n + i) << 1 | 1]);
        init(n >> 1);
    }
    Monoid opIndexAssign(Monoid v, size_t i)
    {
        update(i, v);
        return opIndex(i);
    }
    Monoid opIndex(size_t i)
    {
        return x[i + n];
    }
    private void update(in size_t i, Monoid v)
    {
        auto k = n + i;
        x[k] = v;
        while (k)
        {
            k >>= 1;
            x[k] = operation(x[k * 2], x[k * 2 + 1]);
        }
    }
    Monoid opSlice()
    {
        return opSlice(0, n);
    }
    Monoid opSlice(in size_t a, in size_t b)
    {
        return query(a, b);
    }
    private Monoid query(in size_t a, in size_t b, in size_t k=1, in size_t l=0, size_t r=0)
    {
        if (r == 0)
            r = n;
        if (r <= a || b <= l)
            return Identity;
        if (a <= l && r <= b)
            return x[k];
        immutable mid = (l + r) >> 1, nxt = k << 1;
        return operation(query(a, b, nxt, l, mid), query(a, b, nxt | 1, mid, r));
    }
}

unittest
{
    import std.stdio;
    import std.algorithm : min, swap;
    import std.random : uniform;
{
    auto tree = SegmentTree!(int, min, int.max)([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]);
    foreach (i; 0..10)
    {
        auto p = uniform(0, 15);
        auto q = uniform(0, 15);
        tree[p] = q;
        tree[q] = p;
        if (p > q)
            swap(p, q);
        "[%d..%d): %s => %d".writefln(p, q, tree.x[tree.n+p .. tree.n+q], tree[p..q]);
    }
}
{
    auto tree = SegmentTree!(int, (a, b) => a + b, 0)([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]);
    foreach (i; 0..10)
    {
        auto p = uniform(0, 15);
        auto q = uniform(0, 15);
        tree[p] = q;
        tree[q] = p;
        if (p > q)
            swap(p, q);
        "[%d..%d): %s => %d".writefln(p, q, tree.x[tree.n+p..tree.n+q], tree[p..q]);
    }
}
}

size_t toMPT(size_t n)
{
    if (n == 0)
        return 0;
    size_t y = 1;
    while (y < n && y)
        y <<= 1;
    return y;
}