文章和代码曾经归档至【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 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输入样例:
11
30
35
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$
输出样例:
5
1 1
5 1
7 1
3 3
5 5
输入样例:
1
2
1
1
0
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;
}