LeetCode 307 题「区域和检索 - 数组可修改」是一道经典的数据结构设计题要求实现一个类支持单点更新和区间求和两种操作。为什么不能用普通前缀和如果使用前缀和数组sumRange 查询是 O(1)但 update 更新一个元素后需要 O(n) 时间更新所有后续的前缀和。本题中更新和查询操作频繁交替最坏情况下会达到 O(n²)因此需要用更高效的数据结构。核心解法树状数组 (Binary Indexed Tree)树状数组是最推荐的解法代码短、常数小、效率高。它利用二进制分解的思想将前缀和拆分为若干子区间使得更新和查询都达到 O(log n) 的时间复杂度。核心操作· lowbit(i) i (-i)取最低位的 1 及其后面的 0· 更新从 i 开始不断 i lowbit(i)修改对应节点· 查询前缀和从 i 开始不断 i - lowbit(i)累加对应节点· 区间和sumRange(l, r) query® - query(l-1)Python 实现classNumArray:def__init__(self,nums):self.nlen(nums)self.numsnums[:]self.tree[0]*(self.n1)fori,numinenumerate(nums):self._add(i1,num)def_add(self,i,delta):whileiself.n:self.tree[i]delta ii(-i)def_prefix_sum(self,i):s0whilei0:sself.tree[i]i-i(-i)returnsdefupdate(self,index,val):deltaval-self.nums[index]self.nums[index]val self._add(index1,delta)defsumRange(self,left,right):returnself._prefix_sum(right1)-self._prefix_sum(left)Java 实现模板可直接背诵classNumArray{int[]tree;int[]nums;intn;publicNumArray(int[]nums){this.nnums.length;this.numsnums.clone();this.treenewint[n1];for(inti0;in;i){add(i1,nums[i]);}}privateintlowbit(intx){returnx-x;}privatevoidadd(inti,intdelta){while(in){tree[i]delta;ilowbit(i);}}privateintquery(inti){intans0;while(i0){anstree[i];i-lowbit(i);}returnans;}publicvoidupdate(intindex,intval){intdeltaval-nums[index];nums[index]val;add(index1,delta);}publicintsumRange(intleft,intright){returnquery(right1)-query(left);}}其他解法线段树 (Segment Tree)每个节点维护一个区间的和更新和查询也是 O(log n)。功能比树状数组更强但代码更长、常数更大。本题用树状数组即可线段树作为拓展了解。分块 (Sqrt Decomposition)将数组分成若干块每块维护块内和。update 为 O(1)更新元素和块和sumRange 为 O(√n)。适合作为简单易懂的替代方案但效率不如树状数组。复杂度对比方法 update sumRange 代码量前缀和 O(n) O(1) 短树状数组 O(log n) O(log n) 短线段树 O(log n) O(log n) 长分块 O(1) O(√n) 中等总结本题优先选择树状数组它是「单点修改 区间求和」场景下的标准最优解。建议将树状数组的模板背熟遇到类似题目可以直接套用。