【高级技巧】线段树区间统计：动态数据的进阶查询封装

local tree = {}
local n = 0
local function build(arr)
    n = #arr
    local function bd(node, lo, hi)
        if lo == hi then
            tree[node] = arr[lo]
            return
        end
        local mid = math.floor((lo + hi) / 2)
        bd(2 * node, lo, mid)
        bd(2 * node + 1, mid + 1, hi)
        tree[node] = tree[2 * node] + tree[2 * node + 1]
    end
    bd(1, 1, n)
end

local function update(pos, val)
    local node = 1
    local lo, hi = 1, n
    while lo ~= hi do
        local mid = math.floor((lo + hi) / 2)
        if pos <= mid then
            node = 2 * node
            hi = mid
        else
            node = 2 * node + 1
            lo = mid + 1
        end
    end
end