题面见COGS
分析：这道题，又双叒叕是区间操作，果断线段树啊。刚刚跟某人@dch探(si)讨(bi)关于线段树大法好还是二叉索引树大法好的问题，肯定线段树大法好啦！！！
话说二叉索引树是什么鬼啦，太难了，%dch，%jjq。
线段树大法好！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <cstdio> #define LL long long using namespace std; const int MX = 10005; int n, m; int num[MX]; struct node{ int le, ri; LL sum; }tree[MX*4]; inline int leftt(int a) { return a<<1; } inline int rightt(int a) { return (a<<1)^1; } inline int mid(int a,int b) { return (a+b)>>1; } void biu(int cur,int l,int r) {//建树 if(l==r) { tree[cur].sum=num[l]; tree[cur].le=tree[cur].ri=l; return; } else { biu(leftt(cur),l,mid(l,r)); biu(rightt(cur),mid(l,r)+1,r); tree[cur].sum=tree[leftt(cur)].sum+tree[rightt(cur)].sum; tree[cur].le=l; tree[cur].ri=r; } return; } inline LL ask(int cur, int l, int r) {//查询 if(l==tree[cur].le&&r==tree[cur].ri) { return tree[cur].sum; } else { if(r<=tree[leftt(cur)].ri) return ask(leftt(cur),l,r); else if(l>=tree[rightt(cur)].le) return ask(rightt(cur),l,r); else return ask(leftt(cur),l,tree[leftt(cur)].ri)+ask(rightt(cur),tree[rightt(cur)].le,r); } } inline int get_num() { int ans=0; char tmp; tmp=getchar(); while(tmp<'0'||tmp>'9') tmp=getchar(); while(tmp<='9'&&tmp>='0') { ans=ans*10+tmp-48; tmp=getchar(); } return ans; } int main() { //freopen("sum.in","r",stdin); //freopen("sum.out","w",stdout); int x, y; n=get_num(); LL tmp=0; for(int i=1;i<=n;i++) { scanf("%d",&num[i]); } biu(1,1,n); m=get_num(); for(int i=1;i<=m;i++) { x=get_num(); y=get_num(); tmp=ask(1,x,y); cout<<tmp<<"\n"; } return 0; } |