APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

#C/C++#树状数组模板

2018年6月29日 1770点热度 0人点赞 0条评论

问题模型

现在有一个这样的问题:有一个数组a,,现在给你w次修改,q次查询,修改的话是修改数组中某一个元素的值;查询的话是查询数组中任意一个区间的和。

这个问题很常见,首先分析下朴素做法的时间复杂度,修改是O(1)的时间复杂度,而查询的话是O(n)的复杂度,总体时间复杂度为O(qn)

可能你会想到前缀和来优化这个查询,我们也来分析下,查询的话是O(1)的复杂度,而修改的时候修改一个点,那么在之后的所有前缀和都要更新,所以修改的时间复杂度是O(n),总体时间复杂度还是O(qn)。

可以发现,两种做法中,要么查询是O(1),修改是O(n);要么修改是O(1),查询是O(n)。那么就有没有一种做法可以综合一下这两种朴素做法,然后整体时间复杂度可以降一个数量级呢?有的,对,就是树状数组。

lowbit函数

int lobit(int k) {
	return k & (-k);
}

lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1

树状数组

这是树状数组的模型

可以看出

C1 = A1
C2 = A1+A2
C3 = A3
C4 = A1+A2+A3+A4
C5 = A5
C6 = A5+A6
C7 = A7
C8 = A1+A2+A3+A4+A5+A6+A7+A8

通过lowbit函数来得出k,其中k就是该值从末尾开始0的个数。然后将其得出的结果加上x自身就可以得出当前节点的父亲节点的位置或者是x减去其结果就可以得出上一个父亲节点的位置。

所以他就变成logn的数据结构了

模板

树状数组 1

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数,表示一个操作,具体如下:

操作1: 格式:1 x k 含义:将第x个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出样例#1:
14
16

代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 500005;
int a[maxn];
int n,m; 

int lowbit(int );
void add(int ,int );
int sum(int );

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
   	for(int i = 1;i <= n;++i) {
   		int t;
   		cin >> t;
   		add(i,t);
	}
   	for(int i = 1;i <= m;++i) {
   		int t,x,y;
   		cin >> t >> x >> y;
   		if(t == 1) add(x,y);
   		if(t == 2) cout << sum(y) - sum(x-1) << endl;
	}
	return 0;
}

int lobit(int k) {
	return k & (-k);
}
void add(int i,int t) {
	while(i <= n) {
		a[i] += t;
		i += lobit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while(i) {
		ans += a[i];
		i -= lobit(i); 
	}
	return ans;
}

树状数组 2

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x 含义:输出第x个数的值

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

输出样例#1:
6
10

代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 500005;
int a[maxn];
int n,m; 
int low;

int lowbit(int );
void add(int ,int );
int sum(int );

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
   	for(int i = 1;i <= n;++i) {
   		int t;
   		cin >> t;
   		add(i,t - low);
   		low = t;
	}
   	for(int i = 1;i <= m;++i) {
   		int t;
   		cin >> t;
   		if(t == 1) {
   			int x,y,s;
   			cin >> x >> y >> s;
   			add(x,s);
   			add(y + 1,-s);
		}
   		if(t == 2) {
   			int s;
   			cin >> s;
   			cout << sum(s) <<endl;
		}
	}
	return 0;
}

int lobit(int k) {
	return k & (-k);
}
void add(int i,int t) {
	while(i <= n) {
		a[i] += t;
		i += lobit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while(i) {
		ans += a[i];
		i -= lobit(i); 
	}
	return ans;
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ logn 数据结构 树状数组 洛谷
最后更新:2018年6月29日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
动态规划(DP)方法学习 寿屋:まちカドまぞく シャドウミストレス優子 本博客黑白一周以悼念京都动画及遇难者 #动漫#刀剑神域第一季1-25 1080P 恭喜四叶小天使取得最后的胜利 我没有经验,还真是抱歉呢
标签聚合
动漫 HTML OI 洛谷 ST C++ C/C++ 日常
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang