树状数组
树状数组(Binary Indexed Tree,简称BIT),也被称为Fenwick树,是一种用于处理数组问题的高效数据结构。它特别适合解决涉及区间查询和更新的问题,尤其是当需要频繁地计算数组的前缀和时。树状数组的核心思想是利用二进制表示法(lowbit函数)来快速定位数组中的区间,并在O(log n)时间内完成单点更新和区间查询操作。(树状数组解决的题目,也能用线段树解决(反过来不一定)。但树状数组实现简单,代码短。)
树状数组的基本操作:
更新操作(单点更新):
对于数组中的第 i 个元素,更新树状数组中所有包含该元素的区间。
查询操作(区间查询):
查询数组中从第 i 个元素到第 j 个元素的累积和。
基础知识
lowbit(x)计算——lowbit(x) 可以通过位运算来高效计算。对于一个整数 x,x & (-x) 操作的结果就是 x 的二进制表示中最低位的1。这是因为 -x 的二进制表示中,x 的所有位都被取反,然后加1,这样 x 的最低位的1就变成了0,而其他位都是1。因此,x & (-x) 操作实际上就是将 x 与一个只有 x 最低位的1为1,其他位都是0的数进行与操作。
public int lowbit(int x) {
return x & (-x);
}
单点更新区间查询
public class BinaryIndexedTree {
private int[] tree;
private int size;
public BinaryIndexedTree(int size) {
this.size = size;
tree = new int[size + 1];
}
// 计算小于等于i的最大2的幂次方
private int lowbit(int i) {
return i & (-i);
}
// 单点更新,增加tree[i]的值
public void update(int i, int val) {
while (i <= size) {
tree[i] += val;
i += lowbit(i);
}
}
// 区间查询,计算[1, i]区间的累积和
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
// 区间查询,计算[l, r]区间的累积和
public int query(int l, int r) {
return query(r) - query(l - 1);
}
}
单点修改单点查询
区间修改单点查询
public class FenwickTree {
private int[] tree;
private int[] values;
private int size;
// 构造函数,初始化树状数组和值数组的大小
public FenwickTree(int size) {
this.size = size;
tree = new int[size + 1];
values = new int[size + 1];
}
// 计算小于等于i的最大2的幂次方
private int lowbit(int i) {
return i & (-i);
}
// 更新树状数组,反映值的变化
private void updateTree(int i) {
while (i <= size) {
tree[i] += values[i];
i += lowbit(i);
}
}
// 区间修改,对区间[L, R]内每个元素增加val
public void rangeUpdate(int L, int R, int val) {
values[L] += val;
if (R + 1 <= size) {
values[R + 1] -= val;
}
updateTree(L);
updateTree(R + 1);
}
// 单点查询,查询位置i的值
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return values[i] + sum;
}
}
区间修改区间查询
class NumArray {
private int[] nums;
private int[] tree;
public NumArray(int[] nums) {
int n = nums.length;
this.nums = new int[n]; // 使 update 中算出的 delta = nums[i]
tree = new int[n + 1];
for (int i = 0; i < n; i++) {
update(i, nums[i]);
}
}
public void update(int index, int val) {
int delta = val - nums[index];
nums[index] = val;
for (int i = index + 1; i < tree.length; i += i & -i) {
tree[i] += delta;
}
}
private int prefixSum(int i) {
int s = 0;
for (; i > 0; i &= i - 1) { // i -= i & -i 的另一种写法
s += tree[i];
}
return s;
}
public int sumRange(int left, int right) {
return prefixSum(right + 1) - prefixSum(left);
}
}
标签:树状,int,tree,private,算法,详解,数组,public,size
From: https://blog.csdn.net/w287586/article/details/143106434