前缀和的难题

前缀和只适合“建好后不再改”的情况。一旦修改了 a[k]，从 s[k] 到 s[n] 全都要重算，单次修改就是 O(n)。当修改和查询都很频繁时，前缀和就太慢了，这正是树状数组要解决的问题。