树状数组
作用
- 某个位置加上一个数
- 动态维护前缀和
重要操作:
1. add() 插入操作 O(logn)
2. query() 返回前缀和 O(logn)
3. lowbit()
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tr[N]; //tr[i]表示区间(i - lowbit(i), i]的和
int n, m;
int lowbit(int x)
{
return x & -x;
}
//在下标x及其后面相关联的部分都+v,求前缀和的时候增值在此处已经处理,因为前缀和是分段求的
void add(int x, int v)
{
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()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), add(i, a[i]);
while(m -- )
{
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
if(k == 0) //求[x, y]内的和
printf("%d\n", query(y) - query(x - 1));
else add(x, y);
}
return 0;
}
线段树写法
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int w[N]; //表示叶子节点/原始序列的值
//结构体中每个节点表示一段区间的左右端点及区间和, 由多个这样的节点维护线段树
struct Node{
int l, r;
int sum;
}tr[N * 4]; //记得开4倍
//求出当前节点所表示的区间和求出来
void pushup(int u)
{
//当前节点的区间和=左儿子区间和+右儿子区间和
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
//建树
void build(int u, int l, int r)
{
if(l == r) //表示到了叶子节点
tr[u] = {l, r, w[r]}; //叶子节点的节点标号u的值给到
else //递归的向下找到叶子节点
{
tr[u] = {l, r}; //先将当前节点的左右区间初始化,当前区间的sum将在以下递归回溯的过程中求得
int mid = l + r >> 1; //选定中点,以此左右分半建树
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
//递归“递”的过程完成后已经求得了叶子节点的{l, r, sum},向上回溯去填补上面的sum
pushup(u);
}
}
//传入根节点标号和询问区间[l,r],返回区间[l,r]的和
int query(int u, int l, int r)
{
//如果节点标号u的区间在区间[l,r]内,说明节点标号u的区间和是区间[l,r]的子集
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
//递归寻找[l,r]的子区间和
//当前节点标号u所表示的区间不完全在[l,r]中,那么将该区间划分,递归找到完全在[l,r]中的节点标号区间
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
//在左子树中找[l,r]区间子区间
if(l <= mid) sum = query(u << 1, l, r); //先计算的左子树,所以+ or +=都一样都只会被算一次
if(r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
//传入根节点标号u,在根节点u所表示的区间中找到包括下标为x的节点,并修改该节点的值(此处是+v)
void modify(int u, int x, int v)
{
//找到包含节点x的节点。
if(tr[u].l == tr[u].r) tr[u].sum += v;
else
{
int mid = tr[u].l + tr[u].r >> 1; //从大范围往小范围找
if(x <= mid) //说明下标x是当前节点左儿子的子集,就递归的找到x
modify(u << 1, x, v);
else
modify(u << 1 | 1, x, v);
//将叶子节点修改后要回溯的动态维护整个区间的和
pushup(u);
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
//建树,将1点作为根节点,(1,n)表示区间[1,n],目的是求出[1,n]的和
build(1, 1, n);
while(m -- )
{
int k, a, b;
scanf("%d%d%d", &k, &a, &b);
if(k == 0) printf("%d\n", query(1, a, b)); //从根节点标号1, 开始寻找区间[l,r]的和
else modify(1, a, b); //a为下标,也就是这里说的标号
}
return 0;
}