Segment Tree (update by segment, query by index)

segment-tree.lua

function SegmentTree(size, merge, zero)
    local tree = {}

    local function get(v, tl, tr, index)
        local value = tree[v] or zero
        if tl == tr then
            return value
        end
        local tm = math.floor((tl + tr) / 2)
        if index <= tm then
            return merge(value, get(v * 2, tl, tm, index))
        else
            return merge(value, get(v * 2 + 1, tm + 1, tr, index))
        end
    end

    local function update(v, tl, tr, l, r, add)
        if l == tl and r == tr then
            tree[v] = merge(tree[v] or zero, add)
        else
            local tm = math.floor((tl + tr) / 2)
            if l <= tm then
                update(v * 2, tl, tm, l, math.min(r, tm), add)
            end
            if r >= tm+1 then
                update(v * 2 + 1, tm+1, tr, math.max(l, tm+1), r, add)
            end
        end
    end

    return {
        tree = tree,
        get = function (index)
            return get(1, 1, size, index)
        end,
        update = function (l, r, add)
            return update(1, 1, size, l, r, add)
        end
    }
end