洛谷 P3374 【模板】树状数组 1（树状数组解法）

【题目链接】

洛谷 P3374 【模板】树状数组 1

【题目考点】

一. 树状数组

树状数组是在线算法，可以维护区间和，区间最值。其实现单点修改、区间修改、区间查询时间复杂度都为$O(\log n)$

1. lowbit函数

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

lowbit(x)为x在二进制下最低位的位权，为x在二进制下最低位的1和后面的0组成的数的数值。
例：十进制数$12$在二进制下为$(1100{)}_2$，那么lowbit(12)为$(100{)}_2$，即十进制下的4。

2. 树状数组的定义

设原序列为$a_1,a_2,...,a_n$，$a_i$表示序列的第i个数，共有n个数。
树状数组为$t$，$t_i=\sum _{j=i-lowbit(i)+1}^x{a}_j$，即$t_i$为$a$序列区间$[i-lowbit(i)+1,i]$的区间和，或者说以$a_i$为结尾的长为$lowbit(i)$的区间的区间和。

树状数组满足如下性质：

1. 每个内部结点$t_i$保存以它为根的子树中所有叶子结点的和。
2. 每个内部结点$t_i$的子结点个数等于lowbit(i)的位数。
3. 每个内部结点$t_i$的父结点是$t_{i+lowbit(i)}$。
4. 树状数组下标不能从0开始，必须从1开始。
5. 树的深度为$O(logn)$。

【题目考点】

解法1：树状数组

使用树状数组维护区间和，进行单点修改和区间查询

1. 单点修改

设update函数完成对元素$a_i$的修改，假设$a_i$的值增加$v$（v可以是负数），那么在树状数组表示的树中，所有$a_i$的祖先结点都表示包含$a_i$的一段区间的区间和，因此这些祖先结点的值都要增加$v$。
设循环控制变量x初值为i。每次循环将x增加lowbit(x)，使x变为其父结点，直到x大于n时结束循环。循环体内，树状数组x位置的值$t_x$增加$v$。

2. 区间查询

记$a$序列区间$[1,i]$中元素加和为$s_i$。
设sum函数，调用sum(i)可以求出$s_i$
$a$序列区间$[1,i]$中元素加和为$a$序列$[1,i-lowbit(i)]$中元素的加和再加上$[i-lowbit(i)+1,i]$中元素的加和，即$t_i$。
因此$s_i=s_{i-lowbit(i)}+t_i$
不断使用该递推式，可以将$s_i$分成多个$t$中的元素相加。
设求和变量s初值为0。循环控制变量x初值为i，每次循环x减少lowbit(x)。循环体内让s增加$t_x$。最后s的值即为$s_i$

求a序列区间$[l,r]$中元素的加和，即可用a序列前r项的和减去前l-1项的和求出，即$s_r-s_{l-1}$

使用树状数组维护区间和，每次单点修改的时间复杂度为$O(\log n)$，区间查询的复杂度为$O(\log n)$。

【题解代码】

#include <bits/stdc++.h>
using namespace std; 
#define N 500005
int n, tree[N];//原数组为a，a[i]是输入的第i个数 tree：树状数组 维护区间和 
int lowbit(int x)
{return x & -x;
}
void update(int i, int v)//a[i] += v 单点修改 
{for(int x = i; x <= n; x += lowbit(x))tree[x] += v; 
}
int sum(int i)//a[1]+...+a[i] 区间查询 
{int s = 0;for(int x = i; x > 0; x -= lowbit(x))s += tree[x];return s;
} 
int query(int l, int r)//求[l, r]的区间和 
{return sum(r)-sum(l-1);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int m, x, y, k, v, op;cin >> n >> m;for(int i = 1; i <= n; ++i){cin >> v;update(i, v);}while(m--){cin >> op;if(op == 1){cin >> x >> k;update(x, k);}else{cin >> x >> y;cout << query(x, y) << '\n';}}return 0;
}