树状数组的简单介绍和C++实现
程序员文章站
2022-07-07 15:46:51
...
有关树状数组,大家可以参考网上介绍,这里,我简单介绍一下树状数组的实现:
树状数组作用:可以用于区间查询和单点更新:
比如,查询数组中从下标为2到4的值的和,那么就可以用到区间查询,这里的区间查询函数可以计算从1-n的值,根据个人的需要,就可以利用区间查询来计算出自己需要的值;那么单点更新就是说:可以在某一位加上或者减去某一个数字,同时更新树状数组的值即可。
以上的功能实现都取决于这个树状数组C的建立。
那么C是如何建立的,大家可以在网上查到:
C[i]=A[i-2^ k+1]+A[i-2^k+2]+…+A[i];
其中,A[i]为原始数组,C为树状数组,其中的2^k 表示的就是A数组和C数组之间的关系,也即lowbit操作,具体的可以查看其它网页。
现在我们知道了其基本原理额可有的一些操作,那么我们就可以用它来解决问题,比如:http://acm.hdu.edu.cn/showproblem.php?pid=1166
那么这一题就可以直接用树状数组来解决
#include<iostream>
#include<memory.h>
using namespace std;
const int max_n=1e3;
const int INF=0x7fffffff;
//@author;hairu,wu
/*
http://acm.hdu.edu.cn/showproblem.php?pid=1166
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
6
Add 3 6
Query 2 7
33
Sub 10 2
Add 6 3
Query 3 10
59
End
*/
int c[max_n];//树状数组,有效下标从1开始
//计算2^k操作
int lowbit(int x){
return x&(-x);
}
//单点更新,将x位置的数字加上一个y,同时数组的最大下标为n,
//且x位置后序的也要同时更新
void update(int x,int y,int n){
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=y;
}
}
//获取从1-x之间的和
int getSum(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
int main(){
int t;
int n;
int x,y,z;
string s;
cin >> t;
while(t--){
cin >> n;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
cin >> z;
update(i,z,n); //单点更新i位置
}
while(true){
cin >> s;
if(s=="End"){
break;
}else if(s=="Add"){
cin >> x>>y;
update(x,y,n);
}else if(s=="Sub"){
cin >> x>> y;
update(x,-y,n);
}else if(s=="Query"){
cin >> x>> y;
cout<<getSum(y)-getSum(x-1)<<endl;
}
}
}
return 0;
}
上一篇: 最长连续不重复子串
下一篇: 45. 跳跃游戏 II
推荐阅读
-
C++实现LeetCode(34.在有序数组中查找元素的第一个和最后一个位置)
-
队列的介绍和使用(用数组实现队列操作实例)
-
个人学习笔记:c++数组实现的模板队列和栈
-
树状数组的简单介绍和C++实现
-
简单地介绍Excel中的数组公式为进一步的研究和应用打下基础
-
简单介绍HTML+CSS实现单列布局和水平居中布局的方法
-
JavaScript的String类型replace()方法介绍和使用replace()方法实现简单html模板替换功能...
-
简单介绍HTML+CSS实现单列布局和水平居中布局的方法
-
队列的介绍和使用(用数组实现队列操作实例)
-
js实现数组去重的方法有哪些?js数组去重方法的简单介绍