文章和代码曾经归档至【Github仓库：algorithms-notes】或者公众号【AIShareLab】回复 算法笔记 也可获取。

树状数组

留神：树状数组的坐标肯定要从1开始！

树状数组的利用次要是：疾速（在O(logn)的复杂度内）：

  • 在某个地位上加上一个数（单点批改）
  • 求某一个的前缀和（区间查问）

其余的变式都是由这两个基本功能转换而来，例如单点查问，区间批改等等。

它与纯前缀和的区别在于能够单点批改。如果间接用前缀和进行单点批改，则它每次都会更新批改值前面的前缀和，因而会导致每个都更新一遍，复杂度为O(n)了。

简略的比拟：

单点批改区间查问综合
前缀和O(n)O(1)(O(n) + O(1)) / 2 = O(n)
线段数组O(logn)O(logn)O(logn)

根本思维

其中原数组为A，树状数组为C。每一层的关系如上所示,能够发现，雷同个数的后缀0的数在同一层，比方2--->10, 6 ---> 110。

其中：

  • C[1] = A[1]
  • C[2] = A[2] + C[1] = A[2] + A[1]
  • C[3] = A[3]
  • C[4] = A[4] + C[3] + C[2] = A[4] + A[3] + A[2] + A[1]
  • ...

外围：C[x] = (x - lowbit(x), x]

lowbit = x & -x = $2 ^ k$ 作用是统计二进制数字中后缀0的个数。

模板

在某个地位上加上一个数（单点批改）

// a[x] + v// x 的父节点是 x + lowbit(x)for(int i = x; i <= n; i += lowbit(x))    c[x] += v;

求某一个的前缀和（区间查问）

int res = 0;for(int i = x; i > 0; i -= lowbit(i))    res += c[i];return res

外围函数

// lowbit函数int lowbit(int x){    return x & -x;}
void add(int x, int v){    // i节点的父节点是 i + lowbit(i),每个父节点都要进行批改    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;}
int query(int x){    int res = 0;    // 递归的形式    for (int i = x; i; i -= lowbit(i)) res += tr[i];    return res;}

模板题：动静求间断区间和

给定 n 个数组成的一个数列，规定有两种操作，一是批改某个元素，二是求子数列 [a,b] 的间断和。

输出格局

第一行蕴含两个整数 n 和 m，别离示意数的个数和操作次数。第二行蕴含 n 个整数，示意残缺数列。

接下来 m 行，每行蕴含三个整数 k, a, b （k=0，示意求子数列[a,b]的和；k=1，示意第 a 个数加 b）。数列从 1 开始计数。

输入格局

输入若干行数字，示意 k=0 时，对应的子数列 [a,b] 的间断和。

数据范畴

$1≤n≤100000$,
$1≤m≤100000$，
$1≤a≤b≤n$,
数据保障在任何时候，数列中所有元素之和均在 int 范畴内。

输出样例：

10 51 2 3 4 5 6 7 8 9 101 1 50 1 30 4 81 7 50 4 8

输入样例：

113035

code：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 100010;int n, m;int a[N], tr[N];// 外围操作int lowbit(int x){    return x & -x;}void add(int x, int v){    // i节点的父节点是 i + lowbit(i),每个父节点都要进行批改    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;}int query(int x){    int res = 0;    // 递归的形式    for (int i = x; i; i -= lowbit(i)) res += tr[i];    return res;}int main(){    scanf("%d%d", &n, &m);    // 初始化原数组    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);    // 初始化树状数组    for (int i = 1; i <= n; i ++ ) add(i, a[i]);    while (m -- )    {        int k, x, y;        scanf("%d%d%d", &k, &x, &y);        if (k == 0) printf("%d\n", query(y) - query(x - 1));        else add(x, y);    }    return 0;}

数星星

天空中有一些星星，这些星星都在不同的地位，每个星星有个坐标。

如果一个星星的左下方（蕴含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。

例如，上图中星星 5 是 3 级的（1,2,4 在它左下），星星 2,4 是 1 级的。

例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。给定星星的地位，输入各级星星的数目。

换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输出格局

第一行一个整数 N，示意星星的数目；

接下来 N 行给出每颗星星的坐标，坐标用两个整数 x,y 示意；

不会有星星重叠。星星按 y 坐标增序给出，y 坐标雷同的按 x 坐标增序给出。

输入格局

N 行，每行一个整数，别离是 0 级，1 级，2 级，……，N−1 级的星星的数目。

数据范畴

$1≤N≤15000$,
$0≤x,y≤32000$

输出样例：

51 15 17 13 35 5

输入样例：

12110

code：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 32010;int n;// tr[i]统计x坐标为i的个数int tr[N], level[N];int lowbit(int x){    return x & -x;}void add(int x){    for (int i = x; i < N; i += lowbit(i)) tr[i] ++ ;}// 查问x≤i的坐标的数，即以后星星的等级int sum(int x){    int res = 0;    for (int i = x; i; i -= lowbit(i)) res += tr[i];    return res;}int main(){    scanf("%d", &n);    for (int i = 0; i < n; i ++ )    {        int x, y;        scanf("%d%d", &x, &y);        // 树状数组的下标必须从1开始，因而须要先执行x ++,把所有坐标同一向右平移1即可        x ++ ;        // 为了防止查到本人，在 add 之前就先查问一下        level[sum(x)] ++ ;        // 而后再增加本人即可        add(x);    }    for (int i = 0; i < n; i ++ ) printf("%d\n", level[i]);    return 0;}