1080 线段树练习
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。
输入描述 Input Description
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。
输出描述 Output Description
共m行，每个整数
样例输入 Sample Input
6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
样例输出 Sample Output
22
22
数据范围及提示 Data Size & Hint
1≤N≤100000， m≤10000 。
两个代码都是用指针写的。
代码一：
//codevs 1080 #include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,m; int sz[100010]; struct node { int val,l,r; node * ch[2];//定义指向node这个结构体的指针 }*root=NULL; int sv(node * cur) { return cur?cur->val:0; } void update(node * cur) { cur->val=sv(cur->ch[0])+sv(cur->ch[1]); } void build(node * &cur,int l,int r)/*node * &cur加上取地址符号，可以改变原来实参指针的指向*/ { if(l>r)return ; cur=new node;/*为这个新节点分配一个结构体*/ cur->l=l;cur->r=r;//指定一个区间 if(l==r)cur->val=sz[l];/*当前是一个单节点*/ else { int mid=(l+r)/2; build(cur->ch[0],l,mid); build(cur->ch[1],mid+1,r); update(cur);//建立好左右孩子之后，更新当前的点 } } void add(node * cur,int pos,int delta) { if(cur->l==cur->r)//到了叶节点 { cur->val+=delta; return; } else { cur->val+=delta; int mid=(cur->l+cur->r)/2//二分查找; if(pos<=mid)add(cur->ch[0],pos,delta); else add(cur->ch[1],pos,delta); } } int query(node * cur,int lp,int rp)/*node * cur不加取地址符号，因为是求和不用改变原来指针的值*/ { if(lp<=cur->l&&cur->r<=rp)return cur->val; else { int ans=0; int mid=(cur->l+cur->r)/2; if(lp<=mid)ans+=query(cur->ch[0],lp,rp); if(rp>mid)ans+=query(cur->ch[1],lp,rp); return ans; } } int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&sz[i]); build(root,1,n); cin>>m; for(int i=0;i<m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a==1)add(root,b,c); else printf("%d ",query(root,b,c)); } return 0; }
代码二：
#include<iostream> using namespace std; #include<cstdio> #define INF 100001 int sz[INF],n,m,a,b,c; struct node { int l,r,val; node *child[2]; }*root=NULL; void update(node *cur) { cur->val=cur->child[0]->val+cur->child[1]->val; } void build(node* &cur,int l,int r) { if(l>r) return ; cur=new node; cur->l=l;cur->r=r; if(l==r) { cur->val=sz[l]; cur->child[0]=cur->child[1]=NULL; } else { int mid=(l+r)/2; build(cur->child[0],l,mid); build(cur->child[1],mid+1,r); update(cur); } } void input() { scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&sz[i]); } void add(node* cur,int x,int y) { if(cur->l==cur->r) { cur->val+=y; return; } else { cur->val+=y; int mid=(cur->l+cur->r)/2; if(x<=mid) add(cur->child[0],x,y); else add(cur->child[1],x,y); } } int sum(node* cur,int l1,int r1) { if(cur->l>=l1&&cur->r<=r1) return cur->val; else { int ans=0; int mid=(cur->l+cur->r)/2; if(l1<=mid) ans+=sum(cur->child[0],l1,r1); if(r1>mid) ans+=sum(cur->child[1],l1,r1); return ans; } } int main() { input(); build(root,1,n); scanf("%d",&m); for(int i=1;i<=m;++i) { scanf("%d%d%d",&a,&b,&c); if(a==1) add(root,b,c); else printf("%d ",sum(root,b,c)); } return 0; }