hdu 1166 地兵布阵 【树状数组】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166
题目就不打了,节省点时间,这道题就是简单的单点更新,区间查询,线段树的写法可以参照一下我的这篇博客,https://blog.****.net/LOOKQAQ/article/details/82875187
下面提供一种树状数组的写法,这类题用树状数组写就是一个突破,网上一搜题解也都有!对于数组,我的理解就是向上跳着建立一颗类似树的东西,我在网上找了一个图,
该图 出自博客https://blog.****.net/ljd4305/article/details/10101535,里面知识点讲解的都挺好的!我还是要强调一点,一定要自己动手模拟一遍,这种树状数组只有自己模拟一下,才能体会到其中的细节!
给出我的AC代码:
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4+10;
int n;
ll tree[maxn<<2];
ll lowbit(int i) //控制跳的位数,比如i为2时,这时经过一次lowbit i的值就变成了4,依次类推
{
return i&(-i);
}
ll update(int i,int c) //更新操作
{
while(i<=n)
{
tree[i] += c;
i += i&lowbit(i);
}
return 0;
}
ll query(int x) //查询操作
{
ll sum = 0;
while(x>0)
{
sum += tree[x];
x -= x&lowbit(x);
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
int cass = 1;
int t,a,b,c,x1;
char s[10];
cin>>t;
while(t--)
{
cin>>n;
memset(tree,0,sizeof tree); //初始化为0,别忘了
cout<<"Case "<<cass++<<':'<<endl;
for(int i=1;i<=n;i++) //输入节点的时候将一树状数组建好
{
cin>>x1;
update(i,x1);
}
while(cin>>s)
{
if(s[0] == 'E')
break;
else if(s[0] == 'A') //在给定的a点加上对应的b值
{
cin>>a>>b;
update(a,b);
}
else if(s[0] == 'S') //在给定的a点减去对应的值
{
cin>>a>>b;
update(a,-b);
}
else
{
cin>>a>>b;
cout<<query(b)-query(a-1)<<endl; //输出的是[a,b]区间的数,所以第二项写成a-1
}
}
}
return 0;
}