树状数组 | JAVA 模板
Peach
976
2024.03.22
2024.03.22
发布于 未知归属地
树状数组学习分享

树状数组（也称为Fenwick树）和线段树是两种常见的数据结构，它们在处理数组和序列的问题时非常有用，但存在一些关键的区别。

1.存储方式：树状数组使用数组来存储数据，而线段树则使用树形结构来存储。这种不同的存储方式导致了它们在空间复杂度上的差异。树状数组的空间复杂度相对较低，为O(n)，而线段树的空间复杂度相对较高。
2.操作复杂度：树状数组和线段树都支持查询和更新操作，但它们在操作复杂度上有所不同。树状数组的查询和更新操作的时间复杂度均为O(log n)。而线段树的查询和更新操作的时间复杂度通常也为O(log n)，但具体实现方式可能会导致复杂度略有不同，有时可能会达到O(log^2 n)。
3.功能特性：线段树特别适用于区间修改和区间查询的场景，例如求解区间最大值、区间最小值等问题。它可以将一个区间不断二分，直到最后只剩一个单元区间，从而方便地处理各种区间操作。而树状数组则主要用于数组的单点修改和区间求和。它以一种特殊的方式组织数据，使得可以在O(logN)的时间内查询某个位置之前的所有元素的和。

image.png

具体代码：

public class BinaryIndexedTree {
private int[] bit;

public BinaryIndexedTree(int n) {  
    bit = new int[n + 1];  
}  

// 更新树状数组中的某个元素  
public void update(int index, int delta) {  
    while (index < bit.length) {  
        bit[index] += delta;  
        index += index & -index;  
    }  
}  

// 计算从1到index的前缀和  
public int getPrefixSum(int index) {  
    int sum = 0;  
    while (index > 0) {  
        sum += bit[index];  
        index -= index & -index;  
    }  
    return sum;  
}  

public static void main(String[] args) {  
    BinaryIndexedTree bit = new BinaryIndexedTree(10);  
      
    // 更新元素  
    bit.update(3, 5);  
    bit.update(7, 10);  

    // 计算前缀和  
    System.out.println(bit.getPrefixSum(3)); // 输出 5  
    System.out.println(bit.getPrefixSum(7)); // 输出 15  
    System.out.println(bit.getPrefixSum(10)); // 输出 15  
}

}

评论 (0)