树状数组
- 树形结构,非二叉树
- 基本作用是维护序列前缀和
1 - 思想
比较特殊的一种树形数据结构。
它的每个节点储存的是 前缀区间 的信息(如前缀和),
与其它树形结构不同的是,
它所存储区间的左右端点下标不需要存储
而是可以直接通过节点编号计算出来,
这样就能很好地解决修改时如何更新的问题。
2 - 方法
树状数组示意图:
由图可知,编号为 $i$ 的节点存储的区间范围是
$i-lowbit(i)+1$ ~ $i$ ,
它的父节点编号为 $i+lowbit(i)$ ,
其中 $lowbit(x)$ 指的是 $x\,\&-x$ ,
即 $x$ 的二进制表示中最低一个 $1$ 的位值。
树状数组支持的操作为 单点增加 和 查询前缀和 ,
3 - 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
string op;
struct Node
{
LL val;
// int id;
// int parent = id + lowbit(id);
// int left = id - lowbit(id) + 1;
// int right = id;
} t[N];
//这里写成结构体的形式是为了方便显示它是节点,实际写的时候可以用数组代替
int lowbit(int x)
{
return x & -x;
}
//单点增加
void add(int k, int x)
{
for (int i = k; i <= n; i += lowbit(i)) t[i].val += x;
//重复以下步骤直到i超出n:
//当前节点存储的前缀和+=x
//i来到当前节点父节点
}
//查询前缀和
LL query(int k)
{
LL res = 0;
for (int i = k; i; i -= lowbit(i)) res += t[i].val;
return res;
//重复以下步骤直到i==0
//答案加上该节点控制的区间的和
//i来到前一个区间的总管点(即刚刚i所在区间的左端点的前一个节点)
}
LL get(int l, int r)
{
if (l > r) swap(l, r);
return query(r) - query(l - 1);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
{
LL x;
scanf("%lld", &x);
add(i, x);
}
while (m --)
{
cin >> op;
if (op == "add")
{
int k, x;
scanf("%d%d", &k, &x);
add(k, x);
}
else if (op == "query")
{
int k;
scanf("%d", &k);
printf("%lld\n", query(k));
}
else if (op == "sum")
{
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", get(l, r));
}
}
return 0;
}
orz