[原创]这是一篇被放弃的博客。。不要看了。。（新手千万不要手撸模板）

2016-08-05 13:33:21 Tabris_ 阅读数：1044

博客爬取于2020-06-14 22:43:58
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52128243

今天解除了一下线段树 据自己理解手撸了发建树与查询的操作 的模板

tree
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
# include <iostream>
# include <string>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <stdio.h>
# include <vector>
# include <time.h>

using namespace std;

# define  LL  long long int

int a[1010101];

struct node
{
    int value ;
    int right , left;

}tree[4040404];


int firstbuild(int o,int l,int r)//从第O个节点 开始建树  不断递归 知道最后到叶子节点
{
    tree[o].left  = l;
	tree[o].right = r;
	tree[o].value = 0;

    if(l==r)
    {
    	tree[o].value = a[l];
        return tree[o].value ;
    }
    int mid = (l+r) >> 1;

    tree[o].value=firstbuild(o * 2,l,mid)+firstbuild(o*2+1,mid+1,r);
	return tree[o].value;
}

int query(int o,int &l,int &r)
{
	//printf("%d--->%d %d\n",o,tree[o].left,tree[o].right);

    int sum=0;
    //首先判断是不是属于所要查询的区间
    if(l<=tree[o].left&&tree[o].right<=r)      //如果该区间属于要查询的区间内  就加上  而且不向下递归了  最终的加和一定是这些区间的和 而且不会重复 不会
        sum += tree[o].value;
    else if(tree[o].right<l||r<tree[o].left) ;
    //如果区间有重合部分但又不包含 就要继续递归子节点 寻找区间。。
 	else if(tree[o].left<l||r<tree[o].right)  //区间过大了  就递归缩小区间
        sum += query(o*2,l,r) + query(o*2+1,l,r);
    else  ; //区间完全不重合 就没有在向下查询的必要了

    return sum;
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}


	firstbuild(1,1,n);
	for(int i=1;i<=n*2-1;i++)
		printf("%d %d\n",tree[i].left,tree[i].right);
	puts("");
	int nu=0,un=1;
    for(int i=1;i<=n*2-1;i++)
    {
        if(nu>=un)
        {
            nu=0,un*=2;
            puts("");
        }
        nu++;
        printf("%d ",tree[i].value);
    }
    puts("");
    while(true)
	{
		int l,r;
		cin>>l>>r;
		if(l==0||r==0) break;
		printf("%d\n",query(1,l,r));
	}
	return 0;
}