本文作者:Zhang, Xuheng
本文分类:编程学习笔记 浏览:1808
阅读时间:5168字, 约5.5-8.5分钟
Part 1 基础
树状数组可以解决大部分基于区间上的更新以及求和问题。
树状数组修改和查询的复杂度都是 $O(logn)$,而且相比线段树系数要少很多,比传统数组要快,而且容易写。
缺点是遇到复杂的区间问题还是不能解决,功能还是有限。
单点更新、区间查询
核心:
int a[500005],c[500005];
int lowbit(int x) {
return x & (-x);
}
void updata(int i,int k) { //i的位置加上k
while(i <= n) {
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i) { //求a[1]到a[i]的和
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[500005],c[500005];
int lowbit(int x) {
return x & (-x);
}
void updata(int i,int k) { //i的位置加上k
while(i <= n) {
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i) { //求a[1]到a[i]的和
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
updata(i,a[i]);
}
while(m--) {
int opt;
int x,y;
scanf("%d%d%d",&opt,&x,&y);
if (opt == 1) updata(x,y);
else if (opt == 2) printf("%d\n",getsum(y) - getsum(x - 1));
}
return 0;
}
区间更新、单点查询
这就是第一个问题,如果题目是让你把 $x-y$ 区间内的所有值全部加上k或者减去 $k$ ,然后查询操作是问某个点的值,这种时候该怎么做呢。如果是像上面的树状数组来说,就必须把 $x-y$ 区间内每个值都更新,这样的复杂度肯定是不行的,这个时候,就不能再用数据的值建树了,这里我们引入差分,利用差分建树。
核心:
int n,m;
int a[50005] = {0},c[50005]; //对应原数组和树状数组
int lowbit(int x) {
return x & (-x);
}
void updata(int i,int k) { //在i位置加上k
while(i <= n) {
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i) { //求D[1 - i]的和,即A[i]值
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
updata(i,a[i] - a[i-1]); //输入初值的时候,也相当于更新了值
}
//[x,y]区间内加上k
updata(x,k); //A[x] - A[x-1]增加k
updata(y+1,-k); //A[y+1] - A[y]减少k
//查询i位置的值
int sum = getsum(i);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[500005],c[500005];
int opt,x,y,k;
int lowbit(int x) {
return x & (-x);
}
void updata(int i,int k) { //i的位置加上k
while(i <= n) {
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i) { //求a[1]到a[i]的和
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
updata(i,a[i] - a[i-1]);
}
while(m--) {
scanf("%d",&opt);
if (opt == 1) {
scanf("%d%d%d",&x,&y,&k);
updata(x,k);
updata(y + 1,-k);
}
else if (opt == 2) {
scanf("%d",&x);
printf("%d\n",getsum(x));
}
}
return 0;
}
区间更新、区间查询
还是差分。
int n,m;
int a[50005] = {0};
int sum1[50005]; //(D[1] + D[2] + ... + D[n])
int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])
int lowbit(int x) {
return x & (-x);
}
void updata(int i,int k) {
int x = i; //因为x不变,所以得先保存i值
while(i <= n) {
sum1[i] += k;
sum2[i] += k * (x-1);
i += lowbit(i);
}
}
int getsum(int i) { //求前缀和
int res = 0, x = i;
while(i > 0) {
res += x * sum1[i] - sum2[i];
i -= lowbit(i);
}
return res;
}
int main() {
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a[i];
updata(i,a[i] - a[i-1]); //输入初值的时候,也相当于更新了值
}
//[x,y]区间内加上k
updata(x,k); //A[x] - A[x-1]增加k
updata(y+1,-k); //A[y+1] - A[y]减少k
//求[x,y]区间和
int sum = getsum(y) - getsum(x-1);
return 0;
}
区间更新、区间查询。
注意 $\texttt{long long}$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a1[200005],a2[200005],mian = 0;
ll n,m;
ll lowbit(ll x) {
return x & (-x);
}
void updata(ll x,ll v) {
for(ll p=x; x<=n; a1[x] += v,a2[x] += (ll)v * p,x += lowbit(x));
}
ll getsum(ll x) {
ll res = 0;
for(ll p=x; x; res += (p + 1) * a1[x] - a2[x],x -= lowbit(x));
return res;
}
int main() {
cin>>n>>m;
for(ll i=1,x; i<=n; i++) {
scanf("%lld",&x);
updata(i,x);
updata(i + 1,-x);
}
for(ll i=1,opt; i<=m; i++) {
scanf("%lld",&opt);
if(opt == 1) {
ll l,r,x;
scanf("%lld%lld%lld",&l,&r,&x);
updata(l,x);
updata(r + 1,-x);
}
if(opt == 2) {
ll x;
scanf("%lld",&x);
mian += x;
}
if(opt == 3) {
ll x;
scanf("%lld",&x);
mian -= x;
}
if(opt == 4) {
ll l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",getsum(r) - getsum(l - 1) + (l == 1) * mian);
}
if(opt == 5) printf("%lld\n",getsum(1) + mian);
}
return 0;
}
区间修改,单点查询。
差分建树。
#include <bits/stdc++.h>
using namespace std;
int n,m;
int opt,a,b;
int c[10000005] = {0};
int lowbit(int x) {
return x & (-x);
}
void updata(int i,int k) { //在i位置加上k
while(i <= n) {
c[i] += k;
i += lowbit(i);
}
}
int getsum(int i) { //求D[1 - i]的和,即A[i]值
int res = 0;
while(i > 0) {
res += c[i];
i -= lowbit(i);
}
return res;
}
int main() {
cin>>n>>m;
while(m--) {
scanf("%d",&opt);
if (opt == 0) {
scanf("%d%d",&a,&b);
updata(a,1);
updata(b + 1,-1);
}
else {
scanf("%d",&a);
printf("%d\n",getsum(a));
}
}
return 0;
}
Part 2 进阶
二维树状数组
在一维树状数组中,
```tree[x]```(树状数组中的那个“数组”)记录的是右端点为 $x$,长度为 $lowbit(x)$ 的区间的区间和。
那么在二维树状数组中,可以类似地定义 ```tree[x][y]``` 记录的是右下角为 $(x, y)$,高为 $lowbit(x)$, 宽为 $lowbit(y)$ 的区间的区间和。
单点修改、区间查询
void add(int x, int y, int z) { //将点(x, y)加上z
int memo_y = y;
while(x <= n) {
y = memo_y;
while(y <= n)
tree[x][y] += z, y += y & -y;
x += x & -x;
}
}
void ask(int x, int y) { //求左上角为(1,1)右下角为(x,y) 的矩阵和
int res = 0, memo_y = y;
while(x) {
y = memo_y;
while(y)
res += tree[x][y], y -= y & -y;
x -= x & -x;
}
}
Code:
#include <bits/stdc++.h>
#define re return
#define ll long long
#define lowbit(x) (x&(-x))
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x) {
char c;
bool f=0;
while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
x=c^48;
while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
if(f)x=-x;
}
const int maxn=5000;
ll n,m;
ll c[maxn][maxn];
inline void add(ll x,ll y,ll z) { //将点(x, y)加上z
for(ll i=x; i<=n; i+=lowbit(i))
for(ll j=y; j<=m; j+=lowbit(j))
c[i][j]+=z;
}
inline ll sum(ll x,ll y) { //求左上角为(1,1)右下角为(x,y) 的矩阵和
ll res=0;
for(ll i=x; i; i-=lowbit(i))
for(ll j=y; j; j-=lowbit(j))
res+=c[i][j];
re res;
}
int main() {
ll a,b,x,y,z,opt;
rd(n); rd(m);
while(~(scanf("%lld",&opt))) {
if(opt==1) {
rd(x),rd(y),rd(z);
add(x,y,z);
} else {
rd(a),rd(b),rd(x),rd(y);
printf("%lld\n",sum(x,y) + sum(a - 1,b - 1) - sum(x,b - 1) - sum(a - 1,y));
}
}
return 0;
}
区间修改、单点查询
void add(int x, int y, int z) {
int memo_y = y;
while(x <= n) {
y = memo_y;
while(y <= n)
tree[x][y] += z, y += y & -y;
x += x & -x;
}
}
void range_add(int xa, int ya, int xb, int yb, int z) {
add(xa, ya, z);
add(xa, yb + 1, -z);
add(xb + 1, ya, -z);
add(xb + 1, yb + 1, z);
}
void ask(int x, int y) {
int res = 0, memo_y = y;
while(x) {
y = memo_y;
while(y)
res += tree[x][y], y -= y & -y;
x -= x & -x;
}
}
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14
2021-2-4 16:51 审核通过
682!