树状数组

树状数组 (Binary Indexed Tree(B.I.T), Fenwick Tree) 是一个查询和修改复杂度都为 log(n) 的数据结构。
「前缀和查询」与「单点更新」
直接前驱：c[i] 的直接前驱为 c[i - lowbid(i)]，即 c[i] 左侧紧邻的子树的根。
直接后继：c[i] 的直接前驱为 c[i + lowbid(i)]，即 c[i] 的父结点。
前驱：c[i] 左侧所有子树的根。
后继：c[i] 的所有祖先。

307. 区域和检索 - 数组可修改

单点更新，区间求和。

class NumArray {    int lowbit(int x) {return x & -x;}int query(int i) {int ans = 0;for (; i > 0; i -= lowbit(i)) ans += tree[i];return ans;}void add(int i, int u) {for (; i <= n; i += lowbit(i)) tree[i] += u;}int[] nums, tree;int n;public NumArray(int[] _nums) {nums = _nums;n = nums.length;tree = new int[n + 1];for (int i = 0; i < n; i++) add(i + 1, nums[i]);}public void update(int i, int val) {add(i + 1, val - nums[i]);nums[i] = val;}public int sumRange(int l, int r) {return query(r + 1) - query(l);}
}

时间复杂度：add 操作和 query 的复杂度都是 O(logn)，因此构建数组的复杂度为 O(nlogn)。整体复杂度为 O(nlogn)
空间复杂度：O(n)

315. 计算右侧小于当前元素的个数

「离散化」：把原序列的值域映射到一个连续的整数区间，并保证它们的偏序关系不变。

• 逆序遍历 nums 读取排名；
• 先查询严格小于当前排名的「前缀和」，即严格小于当前排名的元素的个数，「前缀和查询」；
• 给「当前排名」加 1，「单点更新」。

public class Solution {public List countSmaller(int[] nums) {List res = new ArrayList();int len = nums.length;// 离散化 使用二分搜索树方便排序Set set = new TreeSet();for (int x : nums) set.add(x);Map map = new HashMap<>();int index = 1;for (Integer x : set) map.put(x, index++);BIT tree = new BIT(set.size() + 1);// 逆序填表for (int i = len - 1; i >= 0; i--) {index = map.get(nums[i]);tree.update(index, 1);// 查询小于等于 index - 1 的元素有多少res.add(tree.query(index - 1));}Collections.reverse(res);return res;}private class BIT{private int[] tree;private int len;public BIT(int n) {this.len = n;tree = new int[n + 1];}// 单点更新：将 index 这个位置 + 1public void update(int i, int delta) {            for (; i <= len; i += lowbit(i))  tree[i] += delta;}// 区间查询：查询小于等于 index 的元素个数 查询的语义是"前缀和"public int query(int i) {int sum = 0;for (; i > 0; i -= lowbit(i)) sum += tree[i];return sum;}public int lowbit(int x) {return x & (-x);}}
}

218. 天际线问题

327. 区间和的个数

树状数组（离散化）
由于区间和的定义是子数组的元素和，容易想到「前缀和」来快速求解。

对于每个 nums[i] 而言，需要统计以每个 nums[i] 为右端点的合法子数组个数（合法子数组是指区间和值范围为 [lower, upper] 的子数组）。

可以从前往后处理 nums，假设当前处理到位置 k，同时下标 [0, k] 的前缀和为 s，那么以 nums[k] 为右端点的合法子数组个数，等价于在下标 [0, k - 1] 中前缀和范围在 [s - upper, s - lower] 的数的个数。

需要使用一个数据结构来维护「遍历过程中的前缀和」，每遍历 nums[i] 需要往数据结构加一个数，同时每次需要查询值在某个范围内的数的个数。涉及的操作包括「单点修改」和「区间查询」，容易想到使用树状数组进行求解。

但值域的范围是巨大的（同时还有负数域），可以利用 nums 的长度为 10⁵ 来做离散化。需要考虑用到的数组都有哪些：

首先前缀和数组中的每一位 s 都需要被用到（添加到树状数组中）；
同时对于每一位 nums[i]（假设对应的前缀和为 s），我们都需要查询以其为右端点的合法子数组个数，即查询前缀和范围在 [s - upper, s - lower] 的数的个数。
因此对于前缀和数组中的每一位 s，我们用到的数有 s、s - upper 和 s - lower 三个数字，共有 1e51e5 个 ss，即最多共有 3×10⁵ 个不同数字被使用，我们可以对所有用到的数组进行排序编号（离散化），从而将值域大小控制在 3×10⁵ 范围内。

class Solution {int m;int[] tree = new int[100010 * 3];int lowbit(int x) {return x & -x;}void add(int x, int v) {for (int i = x; i <= m; i += lowbit(i)) tree[i] += v;}int query(int x) {int ans = 0;for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];return ans;}public int countRangeSum(int[] nums, int lower, int upper) {Set set = new HashSet<>();long s = 0;set.add(s);for (int i : nums) {s += i;set.add(s);set.add(s - lower);set.add(s - upper);}List list = new ArrayList<>(set);Collections.sort(list);Map map = new HashMap<>();for (long x : list) map.put(x, ++m);s = 0;int ans = 0;add(map.get(s), 1);for (int i : nums) {s += i;int a = map.get(s - lower), b = map.get(s - upper) - 1;ans += query(a) - query(b);add(map.get(s), 1);}return ans;}
}

406. 根据身高重建队列

493. 翻转对

673. 最长递增子序列的个数

1157. 子数组中占绝大多数的元素

1395. 统计作战单位数

class Solution {public int numTeams(int[] rating) {int n = rating.length;int res = 0;for (int j = 0; j < n; j++) {int lm = 0, ll = 0, km = 0, kl = 0;for (int i = 0; i < j; i++) {if (rating[i] < rating[j]) ll++;else lm++;}for (int k = j + 1; k < n; k++) {if (rating[k] < rating[j]) kl++;else km++;}res += ll * km + lm * kl;}return res;}
}

class Solution {    public int numTeams(int[] rating) {int n = rating.length;discrete(rating);int ans = 0;BIT bit = new BIT(n);for (int i = 0; i < n; i++) {int x = rating[i];            int frontSmall = bit.query(x); // 前面比x小的个数int frontLarge = i - frontSmall; // 前面比x大的个数 int backSmall = x - frontSmall;int backLarge = n - 1 - frontSmall - backSmall - frontLarge;ans += frontSmall * backLarge + frontLarge * backSmall;bit.update(x + 1, 1); // 对应 tree 需要 + 1}return ans;}void discrete(int[] nums) {int n = nums.length;int[] tmp = Arrays.copyOf(nums,  n);Arrays.sort(tmp);for (int i = 0; i < n; i++) {nums[i] = Arrays.binarySearch(tmp, nums[i]);}}private class BIT{private int[] tree;private int len;public BIT(int n) {this.len = n;tree = new int[n + 1];}// 单点更新：将 i 这个位置 + 1public void update(int i, int delta) {            for (; i <= len; i += lowbit(i))  tree[i] += delta;}public int query(int i) {int sum = 0;for (; i > 0; i -= lowbit(i)) sum += tree[i];return sum;}public int lowbit(int x) {return x & (-x);}}
}

1409. 查询带键的排列

1505. 最多 K 次交换相邻数位后得到的最小整数

1649. 通过指令创建有序数组

1964. 找出到每个位置为止最长的有效障碍赛跑路线

2179. 统计数组中好三元组数目

2193. 得到回文串的最少操作次数

2250. 统计包含每个点的矩形数目

2286. 以组为单位订音乐会的门票

2407. 最长递增子序列 II

2424. 最长上传前缀

2426. 满足不等式的数对数目