【树状数组区间修改单点查询+分组】HDU 4267 A Simple Problem with Integers

http://acm.hdu.edu.cn/showproblem.php?pid=4267

【思路】

  • 树状数组的区间修改:在区间[a, b]内更新+x就在a的位置+x. 然后在b+1的位置-x
  • 树状数组的单点查询:求某点a的值就是求数组中1~a的和.

  • (i-a)%k==0把区间分隔开了,不能直接套用树状数组的区间修改单点查询
  • 这道题的K很小,所以可以枚举k,对于每个k,建立k个树状数组,所以一共建立55棵树
  • 所以就可以多建几棵树..然后就可以转换为成段更新了~~

【AC】

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int maxn=5e4+;
int tree[][][maxn];
int a[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add(int k,int x,int pos,int val)
{
while(pos<=n)
{
tree[k][x][pos]+=val;
pos+=lowbit(pos);
}
} int query(int k,int x,int pos)
{
int res=;
while(pos)
{
res+=tree[k][x][pos];
pos-=lowbit(pos);
}
return res;
}
int main()
{
while(~scanf("%d",&n))
{
memset(tree,,sizeof(tree));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
int q;
scanf("%d",&q);
while(q--)
{
int tp;
scanf("%d",&tp);
if(tp==)
{
int x,y,k,c;
scanf("%d%d%d%d",&x,&y,&k,&c);
int st=x/k;
if(x%k) st++;
int ed=st+(y-x)/k;
add(k,x%k,st,c);
add(k,x%k,ed+,-c);
}
else
{
int x;
scanf("%d",&x);
int ans=a[x];
int pos;
for(int i=;i<=;i++)
{
pos=x/i;
if(x%i) pos++;
ans+=query(i,x%i,pos);
}
printf("%d\n",ans);
}
}
}
return ;
}

树状数组

上一篇:线段树 poj 3468


下一篇:ASP.NET MVC4+EasyUI+EntityFrameWork5权限管理系统——菜单模块的实现(二)