分享程序员开发的那些事...
更新时间：2022-08-14 23:28:01
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1166
分析：第一次接触到线段树，上网看了一些资料，发现这道题可以用树状数组来代替线段树解决，似乎用起来更方便，于是乎就找了树状数组的资料来看，这里有一个是我从网上摘抄的树状数组的资料 树状数组 不是很齐全，但是初学者已经够用了。里边有基本的模板代码。
这道题是中文题目，题意很简单，就是典型的树状数组，线段树题目。
树状数组解法
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define MAXN 50005 using namespace std; int a[MAXN],c[MAXN]; int N; // 树状数组模板 int Low_bit(int x) { return x & (-x); } void modify(int n,int value) { while(n<=N) { c[n]+=value; n += Low_bit(n); } } int sum(int n) { int sum=0; while(n>0) { sum+=c[n]; n-=Low_bit(n); } return sum; } int query(int i,int j) { return sum(j)-sum(i-1); } int main() { int t,x,y; scanf("%d",&t); char order[10]; for(int i=1;i<=t;i++) { printf("Case %d:\n",i); scanf("%d",&N); memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); for(int j=1;j<=N;j++) { scanf("%d",&a[j]); modify(j,a[j]); } while(scanf("%s",order)&&strcmp(order,"End")!=0) { scanf("%d%d",&x,&y); if(strcmp(order,"Query")==0) printf("%d\n",query(x,y)); else if(strcmp(order,"Add")==0) modify(x,y); else if(strcmp(order,"Sub")==0) modify(x,-y); } } return 0; }
线段树解法：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define MAXN 50005 using namespace std; typedef struct Node { int ld,rd;//左右边界 struct Node *lc,*rc;//左右子树 int value; }Node,Tree; int num[MAXN]; int N; Tree *create(int a,int b) { int mid; Node *node = (Node*)malloc(sizeof(Node)); node->ld=a; node->rd=b; if(b-a>=1) { mid=(a+b)/2; node->lc=create(a,mid); node->rc=create(mid+1,b); node->value=node->lc->value+node->rc->value; } else node->value=num[node->ld];//也可以写成 node->value=a[node->rd]; return node; } int query(Node *node,int x,int y) { if(node->ld==x && node->rd==y)return node->value; int mid = (node->ld+node->rd)/2; if(mid>=y)return query(node->lc,x,y); else if(mid<x) return query(node->rc,x,y); else return query(node->lc,x,mid)+query(node->rc,mid+1,y); } void modify(Node *node,int x,int v) { if(node->ld==node->rd) { node->value+=v; return; } if(node->lc->rd>=x)modify(node->lc,x,v); else if(node->rc->ld<=x)modify(node->rc,x,v); node->value = node->lc->value+node->rc->value; } int main() { int t,x,y,value; Node *root; scanf("%d",&t); char order[10]; for(int i=1;i<=t;i++) { printf("Case %d:\n",i); scanf("%d",&N); for(int j=1;j<=N;j++) scanf("%d",&num[j]); root = create(1,N); while(scanf("%s",order)&&strcmp(order,"End")!=0) { scanf("%d%d",&x,&y); if(strcmp(order,"Query")==0) printf("%d\n",query(root,x,y)); else if(strcmp(order,"Add")==0) modify(root,x,y); else if(strcmp(order,"Sub")==0) modify(root,x,-y); } } return 0; }