首页 > 代码库 > 线段树练习 1,2
线段树练习 1,2
一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。
共m行，每个整数
6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
22
22
1≤N≤100000， m≤10000 。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
对于每个询问输出一行一个答案
3
1
2
3
2
1 2 3 2
2 3
5
数据范围
1<=n<=100000
1<=q<=100000
代码实现：
1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4 int n,m,a,b,c,d;
5 struct nate{int l,r,s;}t[600000];//线段树结构体。
6 void make_tree(int k,int l,int r){//建树。
7 int lson=k*2,rson=k*2+1;//定义左右儿子。
8 t[k].l=l;t[k].r=r;//填充k掌控区间的左右界限。
9 if(l==r){//如果到了叶节点，输入基值。
10 scanf("%d",&t[k].s);
11 return;
12 }
13 int mid=(l+r)/2;//注意mid是中间值偏左。
14 make_tree(lson,l,mid);//建造左子树。
15 make_tree(rson,mid+1,r);//建造右子树。
16 t[k].s=t[lson].s+t[rson].s;//求得k掌控区间的需求值（可以是和值，最小值，最大值等）。
17 }
18 void point_change(int k,int p,int v){//单点修改。
19 int lson=k*2,rson=k*2+1;
20 int l=t[k].l,r=t[k].r;
21 if(l==r){//对目标节点进行修改。
22 t[k].s+=v;
23 return;
24 }
25 int mid=(l+r)/2;
26 if(p<=mid) point_change(lson,p,v);//p在mid左侧，搜索左子树。
27 else point_change(rson,p,v);//p在mid右侧，搜索右子树。
28 t[k].s=t[lson].s+t[rson].s;//更改相关的节点的需求值。
29 }
30 void interval_change(int k,int l,int r,int v){//区间修改。
31 int lson=k*2,rson=k*2+1;
32 if(t[k].l==t[k].r){
33 t[k].s+=v;
34 return;
35 }
36 int mid=(t[k].l+t[k].r)/2;
37 if(l<=mid) interval_change(lson,l,min(r,mid),v);//目前修改区间的左界在中间值左侧，说明左子树上有需要更改的节点，搜索左子树包含区间与目前修改区间的交集。
38 if(r>mid) interval_change(rson,max(l,mid+1),r,v);//目前修改区间的右界在中间值右侧，说明右子树上有需要更改的节点，搜索右子树包含区间与目前修改区间的交集。
39 t[k].s=t[lson].s+t[rson].s;//更改相关节点的需求值。
40 }
41 int point_query(int k,int p){//单点查询。
42 int lson=k*2,rson=k*2+1;
43 int l=t[k].l,r=t[k].r;
44 if(l==r) return t[k].s;
45 int mid=(l+r)/2;
46 if(p<=mid) return point_query(lson,p);
47 else return point_query(rson,p);
48 }
49 int interval_query(int k,int l,int r){//区间查询。
50 int lson=k*2,rson=k*2+1;
51 if(t[k].l==l&&t[k].r==r) return t[k].s;
52 int mid=(t[k].l+t[k].r)/2,ans=0;
53 if(l<=mid) ans+=interval_query(lson,l,min(r,mid));//目前查询区间的左界在中间值左侧，说明左子树仍有用，查询左子树包含区间与目前查询区间的交集。
54 if(r>mid) ans+=interval_query(rson,max(l,mid+1),r);//目前查询区间的右界在中间值右侧，说明右子树仍有用，查询右子树包含区间与目前查询区间的交集。
55 return ans;
56 }
57 int main(){
58 scanf("%d",&n);
59 make_tree(1,1,n);
60 scanf("%d",&m);
61 for(int i=1;i<=m;i++){
62 scanf("%d%d%d",&a,&b,&c);
63 if(a==1){
64
65 }
66 if(a==2){
67
68 }
69 }
70 return 0;
71 }
无注释版高级数据结构基础---线段树的基本实现。
线段树练习 1,2