千问 LeetCode 307.区域和检索 - 数组可修改 Java实现-北京尧图网络

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) 中等总结本题优先选择树状数组它是「单点修改区间求和」场景下的标准最优解。建议将树状数组的模板背熟遇到类似题目可以直接套用。

千问 LeetCode 307.区域和检索 - 数组可修改 Java实现

相关推荐

UE5 UMG图表插件实战：纯C++绘制曲线、饼图、环状图与柱状图

零基础实战Vibe Coding：普通人用AI从0到1做出小工具

从Pi到DSH：Agent Harness如何实现自生长与经验进化

更多资讯

从问答助手到执行Agent：AI编程的质变与实战指南

Claude Code Mod定制全攻略：从配置到自定义命令与钩子脚本

把AI Agent当成实习生来带：任务拆解、配置与代码审查实战指南

ComfyUI本地部署与工作流搭建指南：从零到手把手配置

软件测试用例设计方法详解：从需求拆解到接口用例实践

四臂PEG-NH₂：星形聚乙二醇氨基的结构、偶联与水凝胶应用

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？