树状数组
理论知识
- 需求：
。能够快速计算区间和
。保证在修改了数组的值之后，对相关数据结构内容修改的操作数尽量少
—>同时包含多个节点信息—>树状数组或二叉索引树（Binary Indexed Tree）
- 用途
。能够解决数据压缩里的累积频率的计算问题，现多用于高效计算数列的前缀和、区间和。
。求逆序对
- 特点
。底部确定，顶部无穷大
。最外面的结点是2的n次方
。奇数的结点一定是叶子结点
。数组一定要从1开始
- 复杂度
。它可以以 O(logn) 的时间得到任意前缀和，并同时支持在 O(logn) 时间内支持动态单点值的修改
。空间复杂度 O(n)
- 定义：每一列的顶端节点C数组为树状数组，C[i]代表子树的叶子节点的权值之和
。C[1]=A[1];
。C[2]=A[1]+A[2];
。C[3]=A[3];
。C[4]=A[1]+A[2]+A[3]+A[4];
。C[5]=A[5];
。C[6]=A[5]+A[6];
。C[7]=A[7];
。C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];
- 更新过程：当A5发生改变时，节点的修改过程
。当A5发生改变时，会导致C5—>C6—>C8发送变化，变化的值为A5新值-A5旧值
。101—>110—>1000—>10000
。通过二进制快速获取修改的节点
- 101加最低位1—>110
- 110加最低位10—>1000
- 1000加最低位1000—>10000
- 因此只需要计算出当前节点下标二进制表示的最低位1的位值所表示的值，就可以计算出下一个要修改的节点
- 查询过程：查询下标15的前缀和，从A[0]到A[15]的所有值之和
- 8节点包含了1~8，12节点包含了9~12，14节点包含了13~14，15节点包含了15
- 1111—>1110—>1100—>1000
- 通过二进制快速获取需要的节点
。1111减最低位1—>1110
。1110减最低位10—>1100
。1100减最低位100—>1000
。1000减最低位1000—>0 退出循环
- 实现原理
。获得二进制：取数组下标二进制非0最低位所表示的值
int lowbit(int x) { return x & -x; }
- x & -x：x 与 该数的补码[一个数的负数=这个数的补码=取反+1]相与
- 解释：反码与原码相反，将反码+1后得到的补码由于进位那么最低位的1和原码最低位的1一定是同一个位置，因此通过x & -x可以取出最低位的1
。单点更新：不断反复，直到当前需要修改的节点下标越界即可
void add(int x, int val) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += val ; }
。区间查询：将从A[0]到A[i]的所有值求和
int query(int x){ int sum = 0; for(int i=x;i>0;i-=lowbit(i)){ sum += tr[i]; } return sum; }
- 完整代码【求前缀和】
int n; int[] tr; int lowbit(int x) { return x & -x; } void add(int x, int val) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += val ; } int query(int x){ int sum = 0; for(int i=x;i>0;i-=lowbit(i)){ sum += tr[i]; } return sum; }
- 完整代码【求逆序对】
。对于nums[i]，其左边比它大的nums[j]的个数，即为以nums[i]为右端点的逆序对的数量
。tr[i]代表当前已经遍历到的数组数值小于等于i的总数量
class Solution { int n; int[] tr; int lowbit(int x) { return x & -x; } void add(int x) { for (int i = x; i <= n; i += lowbit(i)) tr[i]++; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public boolean isIdealPermutation(int[] nums) { n = nums.length; tr = new int[n + 10]; add(nums[0] + 1);// 更新tr数组下标0-nums[0]+1 使其数量+1 int a = 0; for (int i = 1; i < n; i++) { a += query(n) - query(nums[i] + 1); // query(n)为当前加入的数的总数，即等于i // query(nums[i] + 1) 为nums[0,i-1]小于等于nums[i] + 1的数量 // 相减即为以nums[i]为右端点的逆序对的数量【全局倒置】 add(nums[i] + 1); } return a; } }
相关题目
全局倒置与局部倒置【LC775】
给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
- 0 <= i < j < n
- nums[i] > nums[j]
局部倒置 的数目等于满足下述条件的下标 i 的数目：
- 0 <= i < n - 1
- nums[i] > nums[i + 1]
当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false
You are given an integer array nums of length n which represents a permutation of all the integers in the range [0, n - 1].
The number of global inversions is the number of the different pairs (i, j) where:
- 0 <= i < j < n
- nums[i] > nums[j]
The number of local inversions is the number of indices i where:
- 0 <= i < n - 1
- nums[i] > nums[i + 1]
Return true if the number of global inversions is equal to the number of local inversions.
暴力
- 思路：暴力… 超时
class Solution { public boolean isIdealPermutation(int[] nums) { int global = 0; int local = 0; int len = nums.length; for (int i = 0; i < len - 1; i++){ if (nums[i] > nums[i+1]){ local++; } for (int j = i + 1; j < len; j++){ if (nums[i] > nums[j]){ global++; } } } return global == local; } }
- 复杂度
。时间复杂度：O ( n 2 )
。空间复杂度：O ( 1 )
数学
- 思路：局部倒置一定是全局倒置，如果除了局部倒置时，还存在其他倒置，那么返回false
- 实现：记录前缀数组nums[0,i-2]的最大值，如果nums[i]<max，那么返回false
- 代码
class Solution { public boolean isIdealPermutation(int[] nums) { int max = 0; for (int i = 2; i < nums.length; i++){ if (nums[i] < max){ return false; } max = Math.max(max,nums[i-1]); } return true; } }
- 复杂度
。时间复杂度：O ( n )
。空间复杂度：O ( 1 )
树状数组
- 思路：对于nums[i]，其左边比它大的nums[j]的个数，即为以nums[i]为右端点的全局倒置的数量
- 实现：使用树状数组统计左边比nums[i]大的个数
。tr[i]代表当前已经遍历到的数组数值小于等于i的总数量
- 代码
class Solution { int n; int[] tr; int lowbit(int x) { return x & -x; } void add(int x) { for (int i = x; i <= n; i += lowbit(i)) tr[i]++; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } public boolean isIdealPermutation(int[] nums) { n = nums.length; tr = new int[n + 10]; add(nums[0] + 1);// 更新tr数组下标0-nums[0]+1 使其数量+1 int a = 0, b = 0; for (int i = 1; i < n; i++) { a += query(n) - query(nums[i] + 1); // query(n)为当前加入的数的总数，即等于i // query(nums[i] + 1) 为nums[0,i-1]小于等于nums[i] + 1的数量 // 相减即为以nums[i]为右端点的逆序对的数量【全局倒置】 b += nums[i] < nums[i - 1] ? 1 : 0; add(nums[i] + 1); } return a == b; } } 作者：宫水三叶 链接：https://leetcode.cn/problems/global-and-local-inversions/solutions/1973365/by-ac_oier-jc7a/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O ( n l o g n )
。空间复杂度：O ( n )
to be continued…
