HDU 1166 树状数组和线段树

本文主要是介绍HDU 1166 树状数组和线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树状数组

#include<bits/stdc++.h>
using namespace std;
long long  data[50001],s[50001],T[50001];
long long  lowbit(long long t)
{return t&(-t);
}
long long  sum(long long  eend)
{long long  sum=0;while(eend>0){sum+=T[eend];eend-=lowbit(eend);}return sum;
}
void pplus(long long  pos,long long  num,long long  ccount)
{while(pos<=ccount){T[pos]+=num;pos+=lowbit(pos);}
}
int main()
{ios::sync_with_stdio(false);string str;int t,n,a,b;cin>>t;for(int i=1; i<=t; i++){cin>>n;T[0]=s[0]=data[0]=0;for(int j=1; j<=n; j++){cin>>data[j];s[j]=s[j-1]+data[j];T[j]=s[j]-s[j-lowbit(j)];}cout<<"Case "<<i<<":"<<endl;while(cin>>str&&str!="End"){cin>>a>>b;if(str=="Query")cout<<sum(b)-sum(a)+data[a]<<endl;else if(str=="Add")pplus(a,b,n),data[a]+=b;else pplus(a,-b,n),data[a]-=b;}}
}

线段树

#include<bits/stdc++.h>
using namespace std;
const int N= 50000;
struct node
{int l,r;long long sum;
};
node tree[N*3];
void buildtree(int l,int r,int pos)
{tree[pos].l=l;tree[pos].r=r;if(l==r){cin>>tree[pos].sum;return ;}int mid=(l+r)>>1;buildtree(l,mid,pos*2);buildtree(mid+1,r,pos*2+1);tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
}
long long query(int l,int r,int pos)
{if(l==tree[pos].l&&r==tree[pos].r)return tree[pos].sum;else if(r<=(tree[pos].l+tree[pos].r)/2)return query(l,r,pos<<1);else if(l>=(tree[pos].l+tree[pos].r)/2+1)return query(l,r,(pos<<1)+1);elsereturn query(l,tree[pos*2].r,pos*2)+query(tree[pos*2+1].l,r,pos*2+1);
}
void update(int pos,int k,int add)
{if(k>=tree[pos].l&&k<=tree[pos].r){tree[pos].sum+=add;if(tree[pos].l==tree[pos].r)return ;update(pos*2,k,add);update(pos*2+1,k,add);}return ;
}
int main()
{ios::sync_with_stdio(false);string str;int t,n,a,b;cin>>t;for(int i=1; i<=t; i++){cin>>n;cout<<"Case "<<i<<":"<<endl;buildtree(1,n,1);while(cin>>str&&str!="End"){cin>>a>>b;if(str=="Query")cout<<query(a,b,1)<<endl;else if(str=="Add")update(1,a,b);else update(1,a,-b);}}return 0;
}

这篇关于HDU 1166 树状数组和线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---