树状数组（bit）是高效支持单点修改与区间求和的数据结构，时间复杂度均为o(log n)，核心基于lowbit(i)=i&(-i)维护前缀和区间；初始化用add构建，单点加和前缀查询均按lowbit跳转，推荐1-based实现，适用于逆序对、动态排名等场景。
树状数组（Binary Indexed Tree，BIT），也叫芬威克树（Fenwick Tree），是一种高效支持单点修改 + 区间求和的数据结构，时间复杂度均为 O(log n)，比线段树更简洁、常数更小，适合纯前缀和类问题。
核心思想：利用二进制低位（lowbit）组织前缀和
每个下标 i 在 BIT 中维护一段区间和：从 i − lowbit(i) + 1 到 i 的元素和。其中 lowbit(i) = i & (−i)（即 i 的二进制表示中最右边的 1 所代表的值）。
比如：
• i = 6（二进制 110），lowbit(6) = 2 → tree[6] 存储 a[5..6] 的和；
• i = 8（1000），lowbit(8) = 8 → tree[8] 存储 a[1..8] 的和。
三个关键操作怎么写
初始化（build）：从空数组开始，对每个位置 i 调用 add(i, a[i])。
单点加（add）：给位置 i 加 delta，然后不断更新所有覆盖 i 的父节点（i += lowbit(i)）。
- public static int lowbit(int x) { return x & (-x); }
- public void add(int i, int delta) { while (i
前缀和查询（query）：从 i 开始，不断累加 tree[i]，再跳到 i − lowbit(i)，直到 i = 0。
- public int query(int i) { int s = 0; while (i > 0) { s += tree[i]; i -= lowbit(i); } return s; }
- 区间 [l, r] 和 = query(r) − query(l−1)，注意下标通常从 1 开始（避免 lowbit(0) 问题）
Java 实现要点与常见坑
BIT 一般用 1-based 数组（tree[1..n]），避免下标 0 带来的逻辑混乱。
数组大小要开 n+1（tree = new int[n+1]）。
修改和查询都必须严格按 lowbit 规则跳转，不能直接遍历。
- 如果原数组下标从 0 开始（如 a[0..n−1]），读入时统一偏移：add(i+1, a[i])
- 多次修改后记得每次 add 都影响后续 query，无需 rebuild
- 不支持区间修改（如 [l,r] 都加 v）——那是线段树或带差分的 BIT 变种的场景
什么时候该选 BIT 而不是线段树？
当你只需要单点更新 + 区间求和/最大值（需额外设计），且不涉及复杂合并（如区间赋值、历史最值等），BIT 更轻量、易写、不易错。
典型场景：逆序对计数、动态前缀和、带修的排名查询。
- 求逆序对：离散化后，从右往左插入并 query(当前值−1)，累计小于它的已插元素个数
- 在线弹幕计数、实时点赞统计等高频单点更新 + 范围汇总场景
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
