`

树状数组

阅读更多

树状数组是一种非常优雅的数据结构.
 
当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.
 
最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.
而树状数组的修改和查询均可在O(log(n))的时间内完成.
 
假设a[1...N]为原数组,定义c[1...N]为对应的树状数组:
c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i]
其中k为i的二进制表示末尾0的个数,所以2^k即为i的二进制表示的最后一个1的权值.
所以2^k可以表示为n&(n^(n-1))或更简单的n&(-n):
 
int lowbit(int n)
{return n& (-n);}
 
对a[n]进行修改后,需要相应的修改c数组中的p1, p2, p3...等一系列元素
其中p1 = n,
       pi+1 = pi + lowbit(pi)
所以修改原数组中的第n个元素可以实现为:
void Modify(int n, int delta)
{
    while(n <= N)
    { c[n] += delta; n += lowbit(n);}
}
 
当要查询a[1],a[2]...a[n]的元素之和时,需要累加c数组中的q1, q2, q3...等一系列元素
其中q1  = n,
       qi+1 = qi - lowbit(qi)
所以计算a[1] + a[2] + .. a[n]可以实现为:
int Sum(int n)
{
     int result = 0;
     while(n != 0)
     { result += c[n]; n -= lowbit(n); }
    return result;
}





树状数组可以扩充到二维。在二维情况下:

C[x][y] = ∑ a[i][j], 其中,
x-lowbit(x) + 1 <= i <= x,
y-lowbit(y) + 1 <= j <= y.

在二维情况下,对应的更新和查询函数为:
void Modify(int x, int y, int delta)
{
    for(int i = x; i <= N; i += lowbit(i))
       for(int j = y; j <= N; j += lowbit(i))
          C[x][y] += delta;
}

int Sum(int i, int j)
{
    int result = 0;
    for(int x = i; x > 0; x -= lowerbit(x))
    {
        for(int y = j; y > 0; y -= lowerbit(y))
        {
            result += C[x][y];
        }
    }

    return result;
}




树状数组可以解决更新线段区间,查询某个点的问题。
在这种情况下,更新线段区间和查询点的时间复杂度仍然为O(logn).

设A[1,N]为我们要处理的数组。
另外设置一个数组B[1,N],使得B[1] + B[2] + .. B[i] = A[i], 其中1 <= i <= N.
即B[i] = A[i] - A[i-1]

当要查询A[i]的时候,我们只需在数组B上使用一般的树状数组操作查询区间[1,i]即可
当我们要给区间A[a~b]加上delta时,只需要在数组B上对B[a]进行一般树状数组的更新delta的操作,同时对数组B上对B[b+1]进行 - delta操作。

这种使用方式同样可以扩展到二维。
二维情况下,
B[i][j] = A[i][j] - A[i-1][j] - A[i][j-1]
当要查询A[i][j]的时候,只需在数组B上查询B[0][0]到B[i][j]的和即可。
当要给矩形A[x1][y1],A[x2][y2]加上delta的时候,只需要在数组B上对B[x1][y1], [x2+1][y2+1]进行一般树状数组的更新delta的操作,同时对B[x1][y2+1], B[x2+1][y1]进行一般树状数组的更新-delta的操作即可。




通过上面的讨论可以看出。树状数组支持对点的更新,对区间和点的查询。

通过稍微改变,可以支持对区间的更新,对点的查询。但是不支持对区间的查询(偶没想出来)。

通过使用线段树,可以支持所有这些操作,包括对区间的更新和对区间的查询。
但是线段树的实现更为复杂,所以能用树状数组解决的问题不需要用线段树。

原文见: http://old.blog.edu.cn/user3/Newpoo/archives/2007/1712628.shtml
分享到:
评论

相关推荐

    树状数组_洛谷_树状数组_

    树状数组,也被称为线段树(Segment Tree),是一种数据结构,主要用于高效地处理动态区间查询和修改问题。在编程竞赛和算法设计中,树状数组是解决许多问题的利器,尤其是在面对需要频繁更新和查询区间信息的问题时...

    算法NOIP树状数组校门外的树.pdf

    树状数组的核心思想是通过特定的二进制索引操作,将一个一维数组转化为类似树形的数据结构,进而利用这种结构简化更新和查询操作。 在树状数组中,我们不直接维护前缀和数组S[],而是将其划分为若干个小区间和,并...

    树状数组树状数组资料下载

    在实际应用中,如“密码机”这类问题,树状数组可以替代线段树来处理异或操作,因为异或操作同样满足交换律和结合律,这使得树状数组能有效地处理这类问题,降低了算法的实现难度。 总的来说,树状数组是一种强大的...

    树状数组 树状数组.ppt

    树状数组 树状数组.ppt

    二维树状数组

    二维树状数组,又称2D线段树,是数据结构中的一个重要概念,主要应用于解决二维区间查询和修改问题。在ACM(国际大学生程序设计竞赛)中,这种数据结构经常被用来提高算法的效率,特别是在处理动态维护区间信息的...

    树状数组资料

    树状数组,也被称为线段树(Segment Tree),是一种数据结构,主要应用于处理区间查询与更新问题,在计算机科学,特别是算法竞赛(如ACM/ICPC)中有着广泛的应用。这个压缩包文件“树状数组资料”很可能包含了关于...

    线段树与树状数组及其在不同场合的使用

    线段树是一种树形数据结构,用于对一个连续的区间进行操作,如求和、查找最大值或最小值等。它将区间分为左子树和右子树,并递归地存储子区间的最大值、最小值或其他信息。线段树的每个节点都对应一个区间,根节点...

    acm 树状数组讲解

    ### ACM树状数组详解 #### 引言 在算法竞赛及数据处理中,频繁地对数组的前缀和进行更新和查询是一项常见的需求。例如,我们需要维护一个数组`A[1]~A[n]`的前缀和`S[i]=A[1]+A[2]+...+A[i]`。如果数组很大且经常...

    树状数组详解

    树状数组,也被称为二进制指数矩阵或 Fenwick 树,是一种用于高效处理动态序列求和问题的数据结构。在给定的题目中,我们可以通过树状数组来快速响应南将军的各种查询,包括计算一段区间内士兵的总杀敌数以及在特定...

    一维和二维树状数组的实现

    树状数组,也被称为线段树(Segment Tree),是一种数据结构,用于高效地处理动态区间查询和更新问题。它在数组的基础上构建一棵二叉树,每个节点存储一个区间(或子数组)的某些属性,例如区间的和。通过树状数组,...

    逆序对(树状数组) C语言

    树状数组,又称为线段树,是一种数据结构,主要用于处理区间查询和区间更新的问题。它的核心思想是将线性数组划分成若干个子区间,每个子区间对应一颗小树,通过这些小树来维护区间的信息。在树状数组中,查询和更新...

    树状数组练习:POJ 3067

    树状数组的核心思想是将一维数组映射到一棵完全二叉树上,每个节点存储对应子数组的累加和。对于任意索引i,其对应的树状数组节点存储了索引[i, 2i)(左闭右开)区间的元素和。这样,我们可以通过一系列的“更新”和...

    线段树和树状数组入门介绍

    线段树和树状数组是两种在ACM(算法竞赛)和编程中广泛使用的高效数据结构,它们主要用于处理数组上的区间查询和修改操作。这里我们将深入理解这两种数据结构的原理和应用。 首先,线段树是一种能够支持动态维护...

    树状数组 后缀数组 字典树 多串匹配算法及启示

    本篇文章将探讨四个关键概念:树状数组、后缀数组、字典树以及多串匹配算法,这些都属于字符串处理和高效计算的重要工具,并提供一些实际应用的启示。 1. **树状数组(Counting Array / Fenwick Tree)** 树状数组...

    java实现的 树状数组

    用java实现的树状数组,可以作为一个简单的模版来进行应用,如果有不懂得地方,可以上网查找树状数组的原理

    树状数组详细讲解.ppt

    树状数组,也被称为二进制索引树(Binary Indexed Tree, BIT),是一种高效的数据结构,主要用于处理动态序列上的区间查询和单点修改问题。它相比于传统的线段树,在编程复杂度、空间复杂度和时间效率上具有优势,...

    树状数组算法的描述和代码的实现

    树状数组,也称为线性基或BIT(Binary Indexed Tree),是一种高效的数据结构,用于处理动态数组上的查询和更新操作。在计算机科学中,尤其是在算法竞赛和数据结构学习中,树状数组是一种非常实用的工具,它能快速...

Global site tag (gtag.js) - Google Analytics