支持单点更新的区间和查询
哪些公司问过
答案要点
- 只查询时前缀和 O(1),但单点更新需 O(n)
- 树状数组每个位置维护长度为 lowbit(i) 的区间和
- 更新:从 k 开始累加 lowbit 向上,更新的是增量,O(log n)
- 区间和 = sum(j)−sum(i−1),查询 O(log n),空间 O(n)
- 需要区间修改或区间最值时用线段树
易错点
- 更新时把新值直接加进去,而不是加差值
- 树状数组下标从 0 开始导致死循环
- 区间和写成 sum(j)−sum(i),少算了 arr[i]
面试官常见追问
- 树状数组和线段树怎么选?
- 树状数组下标为什么从 1 开始?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场