树状数组比前缀和快在动态更新场景：前缀和单点修改需o(n)重建，而树状数组通过lowbit(x)=x&-x实现单点更新和前缀查询均仅o(log n)，其核心是每个下标i维护长度为lowbit(i)的区间和，查[1,i]时不断减lowbit、改i时不断加lowbit。
树状数组比前缀和快在哪？
普通前缀和每次修改都要 O(n)，而树状数组修改和查询都是 O(log n)。关键在它的底层结构——用二进制低位（lowbit）跳转，只维护部分区间和，避免全量更新。
-
lowbit(x)实际就是x & -x，比如lowbit(12)是 4（12 的二进制是 1100，最低位的 1 对应 2²=4） - 每个下标
i管理长度为lowbit(i)的区间：从i - lowbit(i) + 1到i - 所以查
[1, i]时不断减lowbit(i)，改i时不断加lowbit(i)
怎么写标准的树状数组模板？
别手写两套函数，统一用 1-based 下标，封装成 struct 最稳：
struct Fenwick {
vector<long long> tr;
int n;
Fenwick(int n_) : n(n_), tr(n_ + 1, 0) {}
int lowbit(int x) { return x & -x; }
void add(int i, long long v) {
for (; i <ul>
<li>初始化传入数组长度，内部开 <code>n + 1</code> 避免下标越界</li>
<li>
<code>add</code> 是单点加，不是赋值；要初始化原数组，得对每个位置调用 <code>add(i, a[i])</code>
</li>
<li>
<code>sum(i)</code> 返回的是前缀和，不是下标 <code>i</code> 处的值</li>
</ul>
<h3>为什么 update 后 query 结果不对？常见踩坑点</h3>
<p>最常出错的是下标和初始化逻辑：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
</div>
<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>原数组是 0-based，但树状数组必须 1-based：读入 <code>a[0..n-1]</code> 后，要循环 <code>for (int i = 0; i </code>
</li>
<li>修改操作误用赋值而非增量：想把位置 <code>i</code> 改成 <code>v</code>，不能直接 <code>add(i, v)</code>，得先算差值：<code>add(i, v - old_val)</code>
</li>
<li>查询 <code>[l, r]</code> 时传了 0-based 下标，导致 <code>sum(l-1)</code> 变成负数索引——务必确认所有接口参数是 1-based</li>
<li>
<code>tr</code> 数组没初始化为 0，尤其重复使用同一个 <code>Fenwick</code> 实例时，容易残留上一轮数据</li>
</ul>
<h3>树状数组能处理哪些变体问题？</h3>
<p>它不只限于整数加法：</p>
<ul>
<li>支持「单点改、区间查」，反过来「区间改、单点查」也能做（差分 + 树状数组）</li>
<li>支持 long long，但要注意 <code>add</code> 参数类型和 <code>tr</code> 类型一致，混用 int/long long 容易溢出</li>
<li>无法直接支持区间乘、区间 min/max —— 那得换线段树</li>
<li>离散化坐标后可处理大范围下标（比如坐标值到 1e9），只要实际插入点数 ≤ 2e5，树状数组依然高效</li>
</ul>
<p>真正难的不是写对四个函数，而是每次调用前心里清楚：当前下标是不是 1-based？这次是改值还是加增量？查询闭区间时端点有没有偏移？这些细节漏一个，结果就错得毫无征兆。</p></long>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
