树状数组(搬运自维基百科)

树状数组(Fenwick_tree),最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和。它可以以的时间得到,并同样以对某项加一个常数。

基本操作:

  1)新建;

  2)修改;

  3)求和;

lowbit求法:

int lowbit(int x)
{
    return x&(-x);
}

新建:

定义一个数组 BIT,用以维护的前缀和,则:

具体能用以下方式实现:

void build()
{
    for (int i=1;i<=MAX_N;i++)
    {
        BIT[i]=A[i];
        for (int j=i-1; j>i-lowbit(i); j--)
            BIT[i]+=A[j];
    }
}

修改:

假设现在要将的值增加delta,

那么,需要将覆盖的区间包含的值都加上K.

这个过程可以写成递归,或者普通的循环.

需要计算的次数与数据规模N的二进制位数有关,即这部分的时间复杂度是O(LogN)

void edit(int i, int delta)
{
    for (int j = i; j <= MAX_N; j += lowbit(j))
        BIT[j] += delta;
}

求和:

假设我们需要计算的值.

  1. 首先,将ans初始化为0,将i计为k.
  2. 将ans的值加上BIT[P]
  3. 将i的值减去lowbit(i)
  4. 重复步骤2~3,直到i的值变为0
int sum (int k)
{
    int ans = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}
时间: 04-08

树状数组(搬运自维基百科)的相关文章

实用数据结构---树状数组(二叉索引树)

树状数组适用于动态连续和查询问题,就是给定一个区间, 查询某一段的和或者修改某一位置的值. 关于树状数组的结构请去百度百科,否则将看不懂下面内容 我们看这个题 士兵杀敌(二) 时间限制:1000 ms  |  内存限制:65535 KB 难度:5 描述 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的. 小工是南将军手下的军师,南将军经常想知道第m号到第n号士兵的总杀敌数,请你帮助小工来回答南将军吧. 南将军的某次询问之后士兵i可能又杀敌q人,之后南将军再询问的时候,需要考虑到新

初识树状数组

描述 Description 输入一个数列A1,A2-.An(1<=N<=100000),在数列上进行M(1<=M<=100000)次操作,操作有以下两种: (1) 格式为C I X,其中C为字符"C",I和X(1<=I<=N,|X|<=10000)都是整数,表示把把a[I]改为X (2) 格式为Q L R,其中Q为字符"Q",L和R表示询问区间为[L,R](1<=L<=R<=N),表示询问A[L]+-+A

树状数组与线段树

一:树状数组 树状数组是对一个数组改变某个元素和求和比较实用的数据结构.两中操作都是O(logn). 需求:有时候我们需要频繁地求数组的前k项和或者求数组从小标i到j的和,这样每次最坏情况下的时间复杂度就会为O(N),这样效率太低了.而树状数组主要就是为了解决这样一个问题.树状数组在求和及修改都可以在O(lgN)时间内完成. 树状数组需要额外维护一个数组,我们设为C[N],原数组为A[N], 其中每个元素C[i]表示A[i-2^k+1]到A[i]的和,这里k是i在二进制时末尾0的个数.注意通过位

士兵杀敌1(树状数组)

首先,要先讲讲树状数组: 树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构.主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值:经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值. 假设数组a[1..n],那么查询a[1]+...+a[n]的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别. 来观察上面的图: 令

11525 - Permutation(二分+树状数组)

题目链接:点击打开链接 题意:从1~k的所有排列中找到第n个排列, n由公式给出. 思路:可以发现, 这个公式就是康托展开公式(康托展开百科:点击打开链接). 那么s[i]的意思就是i个数中当前数排在第几. 如此, 可以用二分+树状数组快速求解, 和一道BC题目神似. 细节参见代码: #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<st

【51nod】 第K大区间2(二分+树状数组)

[51nod] 第K大区间2(二分+树状数组) 第K大区间2 ﹡    LH (命题人) 基准时间限制:1.5 秒 空间限制:131072 KB 分值: 160 定义一个长度为奇数的区间的值为其所包含的的元素的中位数.中位数_百度百科 现给出n个数,求将所有长度为奇数的区间的值排序后,第K大的值为多少. 样例解释: [l,r]表示区间的值 [1]:3 [2]:1 [3]:2 [4]:4 [1,3]:2 [2,4]:2 第三大是2 Input 第一行两个数n和k(1<=n<=100000,k&l

代码与算法集锦-归并排序+树状数组+快排+深度优先搜索+01背包(动态规划)

归并排序 求逆序数 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 首先考虑下如何将将二个有序数列合并.这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数.然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可. //将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n, int b[], int m, int c

树状数组~讲解

树状数组(Binary Indexed Tree(B.I.T)) 是一个查询和修改复杂度都为log(n)的数据结构.主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值:经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只 能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询).-------摘自百度百科 对于树状数组这种数据结构,关键词一是树状,另一个则是数组. 请看下图: 我们令每个叶节点代表每一个元素. 现在我们变形一下,顺便加上数组的编号:

理解树状数组与POJ 2352

学习自:链接以及百度百科 以及:https://www.bilibili.com/video/av18735440?from=search&seid=363548948825132979 理解树状数组 概念 假设数组a[1..n],那么查询a[1]+...+a[n]的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别. 观察这棵树,容易发现: C1 = A1 C2 = A1 + A2 C3 = A3 C4 = A1 + A2 + A3 + A4 C5 =