求区间和（第 3 到 17 名的战力总和）：前缀和预处理后查询 O(1)，但单点更新要 O(n) 重算整张前缀表；线段树把区间对半分治成一棵树——每个节点存一段区间的聚合值，查询与更新都沿树走 O(log n)。一边改一边查的高频场景（实时榜单调整、动态区间结算）正合适；n 个叶子建树约 2n 个节点。
建树、单点更新与区间查询。示例代码如下：
local seg = {}
local function build(node, lo, hi, vals)
if lo == hi then
seg[node] = vals[lo]
return
end
local mid = math.floor((lo + hi) / 2)
build(node * 2, lo, mid, vals)
build(node * 2 + 1, mid + 1, hi, vals)
seg[node] = seg[node * 2] + seg[node * 2 + 1]
end
local function update(node, lo, hi, pos, val)
if lo == hi then
seg[node] = val
return
end
local mid = math.floor((lo + hi) / 2)
if pos <= mid then
update(node * 2, lo, mid, pos, val)
else
update(node * 2 + 1, mid + 1, hi, pos, val)
end
seg[node] = seg[node * 2] + seg[node * 2 + 1]
end
local function query(node, lo, hi, l, r)
if r < lo or hi < l then
return 0
end
if l <= lo and hi <= r then
return seg[node]
end
local mid = math.floor((lo + hi) / 2)
return query(node * 2, lo, mid, l, r)
+ query(node * 2 + 1, mid + 1, hi, l, r)
end
战力区间接线。示例代码如下：
local powers = { 100, 200, 300, 400 }
build(1, 1, 4, powers)
print(query(1, 1, 4, 2, 4))
update(1, 1, 4, 3, 900)
print(query(1, 1, 4, 2, 4))
第 2 到 4 名的战力和先为 900；第 3 名改成 900 后同区间变 1500——更新与查询都走对数路径。
1000 名玩家的战力表（沙巴克报名数据）：朴素区间求和单次 O(n) 约 0.1 毫秒、每次更新后前缀重算 O(n)；线段树的查询与更新均 O(log n) 约 0.005 毫秒，高频改查场景快 20 倍。内存 2n 节点：1000 玩家约 2000 槽 80KB。
三个不适用场景：一是只查不改——前缀和预处理后 O(1) 查询更简单；二是数据量只有几十条，直接求和微秒级，建树是负优化；三是聚合函数不可合并（如众数无法由两个子区间合成）——线段树的分治前提是聚合可结合。
全站技术干货持续更新：996 引擎 / Lua 实战帖，语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、业务场景 帮会人少时打不死召唤的目标，人多时又抢不到，时机全靠会长手点，纠纷不断。改为每日一次的定时召唤加伤害…
【游戏】 一、业务场景 30 人团本开荒，伤害按个人目标结算，近战几秒就把目标打空，后排毫无参与感。改为全团共享血池：目标总…
【语法】 一、隐蔽陷阱 账目表频繁单点改值又要频繁查前 n 项合计：朴素写法改值一步、查询要扫 n 个元素，查询一多整体就慢…
【游戏】 一、业务场景 想拉动日活，登录礼包要跟着连登天数走：第 1 天小奖，第 7 天大奖。发放核心就一行：按连登天数查阶…
【语法】 一、隐蔽陷阱 大数加法用字符串竖式解决了失真，两笔大数相乘怎么办？tonumber 相乘在 9 位乘 9 位时结果…
【语法】 一、隐蔽陷阱 两批任务分别每 6 分钟与每 8 分钟刷新一次，想知道它们同帧刷新的间隔，从 1 开始逐个试除到 4…