1.0 树状数组概念
【五分钟丝滑动画讲解 | 树状数组 | 21智人马同学】
- 树状数组用于高效计算数组前缀和及支持单点更新操作。与前缀和区别在于树状数组可以在O(log n) 的时间复杂度支持单点更新操作。
其数学证明 参考 树状数组的基本原理
1.1 树状数组的性质
- lowbit函数 : lowbit(i) = i & -i
lowbit(int x)"函数是用来获取一个整数 x 的最低位的 1 所代表的值,也就是 x 的二进制表示中最右边的 1 所在的位置上的数值。 (例如:10 = 1010,lowbit(10) = 2),这个函数常用于树状数组等数据结构中,用于快速定位需要操作的位置或计算位信息。 - 求和性质:序号为i的序列正好就是长度为lowBit(i)且以i结尾的序列.如下图来自 21智人马同学
// 树状数组递归求前缀和函数 public long count(int p) { if (p == 0) { return 0; } return count(p - lowbit(p)) + b[p]; }
- 修改某个值性质:一个序列b[i]正上方的序列,正好就是b[i + lowBit(i)]
因为树状数组每个点维护的是其自身及其前面 lowbit(x) 个位置的区间和,当需要修改某个值时,我们需要更新当前位置及其受影响的后续位置,具体步骤为:
-
首先,修改当前位置p的值。
-
然后,从当前位置
p
开始,沿着树状数组的结构向后更新。对于树状数组中的每个受影响位置,我们需要将其值增加x
。 -
更新完当前位置后,将
p
更新为下一个需要更新的位置,即加上lowbit(p)
,继续进行更新,直到超出数组范围为止。
// 树状数组的单点更新函数 public void add(int p, int x) { while (p < N) { b[p] += x; p += lowbit(p); } }
1.2 BinaryIndexedTree 数据结构
package com.coedes.binaryindextree; /** * @description:树状数组 * @author: wenLiu * @create: 2024/4/22 11:00 */ public class BinaryIndexedTree { private int[] BITree; private int[] nums; // 原始数组 public BinaryIndexedTree(int[] nums) { this.nums = nums; int n = nums.length; this.BITree = new int[n + 1]; // 树状数组使用 1-based 索引 // 初始化树状数组 for (int i = 0; i < n; i++) { update(i, nums[i]); // 利用 update 函数构建初始树状数组 } } // 单点更新:将索引 i 处的元素增加 delta public void update(int i, int delta) { i++; // 转换为树状数组的索引,从 1 开始 while (i < BITree.length) { BITree[i] += delta; i += lowbit(i); // 更新下一个节点 } } // 查询前缀和:查询索引 0 到 i 的元素和 public int query(int i) { i++; // 转换为树状数组的索引,从 1 开始 int sum = 0; while (i > 0) { sum += BITree[i]; i -= lowbit(i); // 向前查询前缀和 } return sum; } // 查询区间 [left, right] 的元素和 public int rangeSum(int left, int right) { if (left > 0) { return query(right) - query(left - 1); } else { return query(right); // left = 0 的情况 } } // 计算 x 的最低位 1 所代表的值,即 lowbit(x) private int lowbit(int x) { return x & (-x); } }
1.3 树形数组应用
1.3.1 动态前缀和
题目描述: 给定一个长度为 n
的初始值为 0 的数组,共进行 m
次操作。每次操作作为一行输入,操作类型由第一个数 op
决定:
- 若
op = 1
,后面接两个整数x
和d
(1 ≤ x ≤ n
,1 ≤ d ≤ 10^5
),表示将数组位置x
的值增加d
。 - 若
op = 2
,后面接两个整数l
和r
(1 ≤ l ≤ r ≤ n
),表示查询数组区间[l, r]
的总和,并输出一个正整数作为结果。
输入描述:
- 第一行输入两个整数
n
和m
(1 ≤ n, m ≤ 100,000
)。 - 接下来
m
行,每行输入三个正整数,表示操作类型和对应的参数。
输出描述:
- 对于每次查询操作,输出一个正整数表示当前区间的和。
input: 4 4 1 2 3 2 1 3 1 3 4 2 2 3 out: 3 7
package com.coedes.binary_index_tree.dynamic_prefix_sum; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @description:动态前缀和 * @author: wenLiu * @create: 2024/4/22 12:06 */ public class Main { static final int N = 100010; static int[] biTree = new int[N]; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] s = reader.readLine().split(" "); int n = Integer.parseInt(s[0]); int m = Integer.parseInt(s[1]); for (int i = 0; i < m; i++) { String[] s1 = reader.readLine().split(" "); int op = Integer.parseInt(s1[0]); int val1 = Integer.parseInt(s1[1]); int val2 = Integer.parseInt(s1[2]); if (op == 1) { add(val1, val2); } else { System.out.println(query(val2) - query(val1 - 1)); } } } private static long query(int p) { long sum = 0; while (p > 0) { sum += biTree[p]; p -= lowbit(p); } return sum; } private static void add(int p, int val) { while (p <= N) { biTree[p] += val; p += lowbit(p); } } private static int lowbit(int p) { return p & (-p); } }
1.3.2 求逆序对数量
逆序对是指数组中所有满足 i < j 且 ai > aj的位置对(i, j),要求计算长度为n的数组中的逆序对总数。
朴素法
for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(a[i]>a[j]){ cnt++; } } }
树形数组法:
add(x,1)的意义就是当前数值为的数字出现次数+1,
从右往左统计,即统计比当前位置 i 的 ai 小的值的元素个数例如求[3 2 1 4]逆序对个数:
query:3(4-1)
bt :0 0 0 1
query:0
bt :1 1 0 2
query:1
bt :1 2 0 3
query:2
bt :1 2 1 4
package com.coedes.binary_index_tree.reverse_order; /** * @description:TODO * @author: wenLiu * @create: 2024/4/22 12:42 */ import javax.sound.midi.Soundbank; import java.util.Scanner; public class Main { static final int N = (int)1E5 + 10; static int[] tr = new int[N]; static int n; static int[] a = new int[N]; static int lowbit(int x) { // 计算最后一位1的位置 return x & -x; } static void add(int x, int d) { // 在第x位置上+d for (int i = x; i <= n; i += lowbit(i)) { tr[i] += d; } } static long query(int x) { // 求1~x的和(前缀和) long ans = 0; // 开long long,省的爆int for (int i = x; i > 0; i -= lowbit(i)) { ans += tr[i]; } return ans; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } long cnt = 0; // 逆序对个数 for (int i = n - 1; i >= 0; i--) { System.out.println("query:" + (a[i] - 1)); int num = (int)query(a[i] - 1); // 查询比a[i]小的元素数量 cnt += num; add(a[i], 1); // 将当前元素添加到树状数组中 for (int i1 = 0; i1 < n + 1; i1++) { System.out.print(tr[i1]+" "); } System.out.println(); } System.out.println(cnt); } }
标签:树状,int,lowbit,static,数组,query From: https://www.cnblogs.com/alohablogs/p/18150083