树状数组简介及代码模板

树状数组是一种基于二进制来将区间 [1, x] 分成 logx 个小区间的数据结构，其基本用途是维护序列的前缀和。

它可以在 O(logn) 的时间复杂度内实现单点修改、单点查询和区间查询。

但是如果进行区间修改，复杂度就是 O(nlogn) 的。

如果要进行区间修改，可以利用差分的思想，记录每次修改的影响，进行两次单点修改来修改首尾端点。复杂度为 O(logn)

树状数组的基本操作：

1、lowbit，返回x的二进制数下最小2的次幂。

2、ask，查询前缀和。

3、add，单点修改。

4、因为 ask 可以查询前缀和，所以也可以使用 ask 来进行单点查询和区间查询。

树状数组的基本组成：

1、a 数组，表示给定的原序列

2、c 数组，c[x]表示 a 的区间 [x - lowbit(x) + 1, x] 的和

lowbit 操作：

lowbit(x)：返回x的二进制数下最小2的次幂

例如：

因为7 = 0111，所以lowbit(7) = 1

因为6 = 0110，所以lowbit(6) = 2

因为4 = 0100，所以lowbit(4) = 4

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

ask 操作：

ask(x)：查询 [1, x] 的前缀和。时间复杂度：O(logx)

ll ask(int x)
{
ll ans = 0;
for (; x; x -= lowbit(x))
ans += c[x];
return ans;
}

add 操作：

add(x, y)：对 a[x] 加上y，同时维护前缀和。时间复杂度：O(logx)

void add(int x, ll y)
{
for (; x <= n; x += lowbit(x))
c[x] += y;
}

代码模板：

使用到了单点修改和区间查询

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
int n, m, a[N]; // a 为原数组 
ll c[N]; // c 为树状数组 
// 返回 x 的二进制数下最小2的次幂 
int lowbit(int x)
{
return x & -x;
}
// 查询前缀和 
ll ask(int x)
{
ll ans = 0;
for (; x; x -= lowbit(x))
ans += c[x];
return ans;
}
// 单点增加 
void add(int x, ll y)
{
for (; x <= n; x += lowbit(x))
c[x] += y;
}
int main(void)
{
int op, x;
ll y;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
add(i, a[i]);
}
while (m--) {
scanf("%d%d%lld", &op, &x, &y);
if (op == 1) {
add(x, y);
} else {
ll res = ask(y) - ask(x - 1);
printf("%lldn", res);
}
}
return 0;
}

最后

以上就是仁爱黄蜂为你收集整理的树状数组简介及代码模板的全部内容，希望文章能够帮你解决树状数组简介及代码模板所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。