首页 > 编程语言 >【算法笔记】树状数组/Binary Indexed Tree/Fenwick Tree

【算法笔记】树状数组/Binary Indexed Tree/Fenwick Tree

时间：2024-09-08 23:28:03浏览次数：4  
标签：Binary le 树状 int lowbit Fenwick Tree 数组 mathcal

前言

树状数组，即树形存储的数组，又称Binary Indexed Tree或Fenwick Tree。
抛开它树形的存储结构，这种神奇的数据结构的应用看起来与「 树」没什么关系：

有一个序列\(A=(A_1,A_2,\dots,A_N)\)，在不超过\(\mathcal O(\log N)\)的时间复杂度内完成下列操作：
\(\to~\)求\([L,R]\)区间内所有数之和。
\(\to~\)指定一个元素\(A_x\)，将其加上\(k\)。

如果想要使求和操作尽可能快，很容易想到前缀和，这样求和操作只要\(\mathcal O(1)\)的时间，但更新操作的时间复杂度就升至\(\mathcal O(N)\)，无法满足题目要求；反之，若直接暴力维护\(A\)中所有元素的值，则虽然更新操作只需要\(\mathcal O(1)\)，但求和操作的时间又变成了\(\mathcal O(N)\)，还是满足不了要求。那有没有一种算法，综合了两种方式的优势，达到题目时间要求呢？

肯定有，那就是今天说的——树状数组。

基本算法

洛谷 P3374【模板】树状数组 1
同“前言”中的部分，\(1\le n,m\le 10^5\)，其中\(m\)为操作总次数。

由于\(n,m\le 10^5\)，所以\(\mathcal O(nm)\)的暴力解法肯定行不通，需要使用\(\mathcal O(M\log N)\)的树状数组。其存储结构大致上是这样的：
树状数组结构

是不是已经有些明白了？这里我们我们把\(B\)当作树状数组的内部存储，则据图可知：

  • \(B_1=A_1\)
  • \(B_2=A_1+A_2\)
  • \(B_3=A_3\)
  • \(B_4=A_1+A_2+A_3+A_4\)
  • \(B_5=A_5\)
  • \(B_6=A_5+A_6\)
  • \(B_7=A_7\)
  • \(B_8=A_1+A_2+A_3+A_4+A_5+A_6+A_7+A_8\)
  • ..

可以看出，\(B_i=A_{i-2^k+1}+A_{i-2^k+2}+\dots+A_i\)，其中\(k\)为\(i\)在二进制下末尾\(0\)的的个数。换句话说，\(2^k\)就是\(i\)在二进制中的的lowbit。

关于lowbit函数
\(\to~\)lowbit的定义：

  • \(\mathrm{lowbit}(0)\) 无意义。
  • 对于任意\(x > 0\)，\(\mathrm{lowbit}(x)=2^k\)，其中\(k\)为\(x\)在二进制下末尾\(0\)的的个数。

\(\to~\)举例：\(\mathrm{lowbit}(10010)=10\)；\(\mathrm{lowbit}(10000)=10000\)
\(\to~\)C/C++实现：

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

或宏定义形式：

#define lowbit(x) (x) & -(x)

根据lowbit函数，上述公式可以写作：

\[l:=i-\mathrm{lowbit}(i)+1\\ r:=i\\ B_i=\sum_{j=l}^{r} A_j \]

按照这样，就可以在\(\mathcal O(\log n)\)的时间复杂度内求\([0,x]\)中整数之和（prefixSum(x)）或将\(A_x\)加上\(k\)（update(x, k)）。
对于\([L,R]\)的区间之和，可以按照segmentSum(l, r) = prefixSum(r) - prefixSum(l - 1)的方式进行计算。详见代码：

#include <cstdio>
using namespace std;

template <typename value_type>
class fenwick_tree {
private:
	const int n;
	value_type* a;
	inline int lowbit(int x) { return x & -x; }
public:
	inline fenwick_tree(int m): n(m) {
		a = new value_type[n + 1];
		for(int i=0; i<=n; i++)
			a[i] = 0;
	}
	inline ~fenwick_tree() { delete[] a; }
	inline value_type prefixSum(int i) {
		value_type res = 0;
		for(; i; i-=lowbit(i)) res += a[i];
		return res;
	}
	inline value_type segmentSum(int l, int r) {
		return prefixSum(r) - prefixSum(l - 1);
	}
	inline void update(int i, const value_type& d) {
		for(; i<=n; i+=lowbit(i))
			a[i] += d;
	}
};

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	fenwick_tree<int> bit(n);
	for(int i=1; i<=n; i++)
	{
		int a;
		scanf("%d", &a);
		bit.update(i, a);
	}
	while(m--)
	{
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if(op == 1) bit.update(x, y);
		else printf("%d\n", bit.segmentSum(x, y));
	}
	return 0;
}

在洛谷 P3374上提交耗时仅\(572\mathrm{ms}\)，同题用同样为\(\mathcal O(\log N)\)的线段树耗时约\(2.5\mathrm{s}\)，可见相比于线段树算法，使用树状数组不仅代码量小、容易实现，还有运行速度快等等优势。

基础算法到此为止，下面来看一些经典的扩展应用。

扩展应用

知识补充：离散化
对于序列\(A=(A_1,A_2,\dots,A_N)\)，我们将\(A\)中的每个数都按原先的映射到一个\([1,N]\)的范围内，这个过程被称为离散化。一般来说，离散化时同样的元素映射到同样的值，不同的元素映射到不同的值，且满足原先的大小关系。换句话说，令原先的序列为\((A_1,\dots,A_N)\)，离散化后的序列为\((B_1,\dots,B_N)\)，则满足如下条件：

  • \(1\le B_i\le N\)（\(1\le i\le N\)）
  • 若\(i \ne j\)，且\(A_i<A_j\)，则\(B_i<B_j\)。
  • 若\(i \ne j\)，且\(A_i=A_j\)，则\(B_i=B_j\)。
  • 若\(i \ne j\)，且\(A_i>A_j\)，则\(B_i>B_j\)。

1. 求逆序对

逆序对问题是经典的序列问题。众所周知，这类问题可以用归并排序在\(\mathcal O(N\log N)\)的时间内解决。不过，既然今天讲的是树状数组，那就不能用归并排序，就主要来说一说树状数组的解法。

洛谷 P1908 逆序对
给定一个整数序列\(A=(A_1,A_2,\dots,A_N)\)，求其中逆序对的个数。
一个整数对\((i,j)\)被称为“逆序对”，当且仅当如下条件满足：
\(\to1\le i<j\le N\)
\(\to A_i>A_j\)
数据范围：\(N\le 10^5,A_i\le 10^9\)。

由于\(N\le 10^5\)，所以暴力的\(\mathcal O(N^2)\)做法肯定不行。
我们考虑使用树状数组，先将数组离散化成\([1,N]\)之间的数，记离散化后的序列为\(B=(B_1,\dots,B_N)\)。我们按\((\)总数对数量\()-(\)非逆序对数量\()=(\)逆序对数量\()\)的公式计算，其中总数对的数量为\(1+2+\dots+N-1=\frac {N(N-1)}2\)。用树状数组维护每个数字的出现次数，则非逆序对的数量可以在遍历\(B\)中的每个元素时动态计算。详见代码。

#include <cstdio>
#include <algorithm>
#define maxn 500005
using namespace std;

inline int read() {
	static char c;
	while((c = getchar()) < '0' && c > '9');
	int res = c ^ 48;
	while((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c ^ 48);
	return res;
}

template <typename value_type>
class fenwick_tree {
private:
	const int n;
	value_type* a;
	inline int lowbit(int x) { return x & -x; }
public:
	inline fenwick_tree(int m): n(m) {
		a = new value_type[n + 1];
		for(int i=0; i<=n; i++)
			a[i] = 0;
	}
	inline ~fenwick_tree() { delete[] a; }
	inline value_type prefixSum(int i) {
		value_type res = 0;
		for(++i; i; i-=lowbit(i)) res += a[i];
		return res;
	}
	inline void update(int i, const value_type& d) {
		for(++i; i<=n; i+=lowbit(i))
			a[i] += d;
	}
};

int a[maxn], rk[maxn];

int main()
{
	int n = read();
	for(int i=0; i<n; i++)
		a[rk[i] = i] = read();
	stable_sort(rk, rk + n, [&](int x, int y) -> bool {
		return a[x] < a[y];
	}); // 因为可能会有重复的数字，所以必须使用稳定的stable_sort排序，用sort只有40分
	fenwick_tree<int> bit(n); // 初始化树状数组，离散化之后大小为n就行
	long long ans = n * (n - 1LL) >> 1LL; // 总数对个数
	for(int i=0; i<n; i++)
	{
		ans -= bit.prefixSum(rk[i]); // 减去非逆序数对，即prefixSum(b[i])
		bit.update(rk[i], 1); // 动态更新当前元素出现次数
	}
	printf("%lld\n", ans);
	return 0;
}

习题：CF1676H2 Maximum Crossings (Hard Version)

2. 区间更新

用过线段树的都知道，树状数组最大的缺点就是无法直接实现区间更新。不过，在一些特殊情况[1]下，我们可以通过差分+离散化来间接实现区间的更新。先来看洛谷上的模板：

P3368【模板】树状数组 2
已知一个长为\(N\)的数列，你需要进行下面两种操作：

  • 1 x y k：将\([x,y]\)区间内的每个数都加上\(k\)。
  • 2 x：求第\(x\)个数的值。

运用差分的思想，用树状数组维护\(A\)的差分数组\(B\)（\(B_i=A_i-A_{i-1}\)）。
此时，我们可以把“区间\([x,y]\)中所有元素都加上\(k\)”看作：

  • \(B_x:=B_x+k\)
  • \(B_{y+1}:=B_{y+1}-k\)

此时，\(A_x=B_1+\dots+B_x\)，正好是树状数组的前缀和操作。
于是，我们在\(\mathcal O(N\log N)\)的时间复杂度内解决了这个问题。

C++实现如下（此实现方式与前面讲的略有不同）：

#include <cstdio>
#define maxn 500005
using namespace std;

template <typename value_type>
class fenwick_tree {
private:
	const int n;
	value_type* a;
	inline int lowbit(int x) { return x & -x; }
public:
	inline fenwick_tree(int m): n(m) {
		a = new value_type[n + 1];
		for(int i=0; i<=n; i++)
			a[i] = 0;
	}
	inline ~fenwick_tree() { delete[] a; }
	inline value_type prefixSum(int i) {
		value_type res = 0;
		for(; i; i-=lowbit(i)) res += a[i];
		return res;
	}
	inline void update(int i, const value_type& d) {
		for(; i<=n; i+=lowbit(i))
			a[i] += d;
	}
};

int a[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++)
		scanf("%d", a + i);
	fenwick_tree<int> bit(n);
	while(m--)
	{
		int op;
		scanf("%d", &op);
		if(op == 1)
		{
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			bit.update(l, k);
			if(r < n) bit.update(r + 1, -k);
		}
		else
		{
			int x;
			scanf("%d", &x);
			printf("%d\n", a[x] + bit.prefixSum(x));
		}
	}
	return 0;
}

习题

总结

树状数组支持更新、求和两种操作。欢迎大家前来提问或补充~
求三连qwq

  1. 实际上所有情况都可以，不过其他的非特殊情况实现起来非常繁琐，有时还不如直接用线段树来得方便，因此这里忽略这种情况。 ↩︎

标签：Binary,le,树状,int,lowbit,Fenwick,Tree,数组,mathcal
From： https://www.cnblogs.com/stanleys/p/18403702/algonotes-fenwick-tree

相关文章

  • C++笔记19•数据结构:红黑树(RBTree)•
    红黑树1.简介：    红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。当搜索二叉树退化为单支树时，搜......
  • Hive 比较BIGINT类型和Binary类型
    鱼弦：公众号：红尘灯塔，CSDN内容合伙人、CSDN新星导师、51CTO(Top红人+专家博主) 、github开源爱好者（go-zero源码二次开发、游戏后端架构https://github.com/Peakchen）HiveBIGINT类型和Binary类型比较HiveBIGINT类型和Binary类型都是用于存储数字数据的类型。它们之间有以下区别：1.......
  • AT_aising2019_e Attack to a Tree 题解
    挺有意思的树型dp。思路发现直接求解很难对限制下手。但我们可以注意到答案最多为\(n\)。考虑将答案记录dp状态。我们可以记\(dp_{i,j}\)为子树\(i\)合法并且断了\(j\)条边的状态。由于合法状态有两种，并且不好一起考虑，所以可以再在dp状态中加一维。令\(dp_{i,......
  • zTree树形菜单交互选项卡效果实现
    1、添加自定义属性page 2、为ztree每个树形节点，添加点击事件1<!DOCTYPEhtml>2<html>34<head>5<metacharset="UTF-8">6<title>ztree树形菜单的使用</title>7<!--导入jquery核心类库-->8......
  • lxml官方入门教程（The lxml.etree Tutorial）翻译
    lxml官方入门教程（Thelxml.etreeTutorial）翻译说明：首次发表日期：2024-09-05官方教程链接：https://lxml.de/tutorial.html使用KIMI和豆包机翻水平有限，如有错误请不吝指出这是一个关于使用lxml.etree处理XML的教程。它简要概述了ElementTreeAPI的主要概念，以及一些简单的增强......
  • [ARC171C] Swap on Tree
    MyBlogs[ARC171C]SwaponTree科技改变生活。以6ms的速度拿下了目前最优解（如果已经确定了\(u\)的一个儿子\(v\)内部的操作顺序，考虑在某个时刻交换\((u,v)\)。设\(a[1,k]\)是操作\(v\)子树内部时\(v\)上面的颜色，可以发现在第\(i\)个时刻交换和在第\(j\)个时......
  • DevExpress WinForms v24.1亮点- TreeList、折叠组件全新升级
    DevExpressWinForms拥有180+组件和UI库，能为WindowsForms平台创建具有影响力的业务解决方案。DevExpressWinForms能完美构建流畅、美观且易于使用的应用程序，无论是Office风格的界面，还是分析处理大批量的业务数据，它都能轻松胜任！DevExpressWinForms控件2024年第一个重大版本......
  • react diff 学习之tree diff
    treediff主要针对的是reactdom节点跨层级的操作。什么是跨层级的操作呢？除同级之外的操作都是跨层级。比如A节点下有B和C，A的同级有个小狗节点，现在把整个A节点移到小狗节点下。对于这种跨层级操作，react只会进行创建和删除操作，当根节点发现子节点A消失了，就会直接销毁A，当小狗节点......
  • npm install时一直idealTree:npm: sill idealTree buildDeps的解决方案
    修改下镜像的地址。1、采用新的镜像地址，进入cmd之后输入：//1.npm的命令npmconfigsetregistryhttps://registry.npmmirror.com//2.yarn的命令yarnconfigsetregistryhttps://registry.npmmirror.com2、查看是否安装成功：//npm的命令npmconfiggetregi......
  • DevExpress WinForms v24.1亮点- TreeList、折叠组件全新升级
    DevExpressWinForms拥有180+组件和UI库，能为WindowsForms平台创建具有影响力的业务解决方案。DevExpressWinForms能完美构建流畅、美观且易于使用的应用程序，无论是Office风格的界面，还是分析处理大批量的业务数据，它都能轻松胜任！DevExpressWinForms控件2024年第一个重大版本——......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99