简单线段树过程详解

#include<iostream>       //——————————>debug 了一上午才把这个程序运行的过程在脑子里有了思路 
#include<string.h>       //头文件就不多说了 
#include<stdlib.h>
#define maxsize 10000  //这个可定义其他数----------->这个 主要是控制数组的大小， 
using namespace std;
struct node {                      //结构体 ，相当于创建的二叉树 
    int left, right;               //记录的左右子节点 
    int lazy, sum;                 //lazy记录延迟，sum记录在这个节点的左右端点之间的总和 
    int mid() { return (left + right) / 2; }
}T[maxsize<<2];//相当于扩大了4倍----------------------->这个时学过数据结构的都知道度为0的比度为2的多1有n个数说明n个叶子节点要建立2*n-1个点但是 
               //因为假若数据相对较大，则访问到了最后一行，则可能用到   n<<1  这种情况就会越界会re所以开4倍 
void pushup(int rt)        //向上更新sum的值 
{
    T[rt].sum = T[rt << 1].sum + T[rt << 1 | 1].sum;
}
void pushdown(int rt, int m)  //向下更新lazy和sum的值，主意好区间，因为整篇都是做区间的多于右区间 
{   
    if (T[rt].lazy)
    {
        T[rt << 1].lazy += T[rt].lazy;
        T[rt << 1 | 1].lazy += T[rt].lazy;   //更新lazy值 
        T[rt<<1].sum += T[rt].lazy*(m - (m >> 1));//这说明如果是n为奇数 则左半部分就是多1
        T[rt<<1|1].sum += T[rt].lazy *(m >> 1);//注意>>的优先级
        T[rt].lazy = 0; //不能忘了把这个标志置为0
    }
}
void create(int rt, int l, int r)
{
    T[rt].left = l;                             //创建时对左节点和右节点进行赋值 
    T[rt].right = r;
    T[rt].lazy = 0; 
    if (T[rt].left == T[rt].right)              //不能写下边了，且只有当到也叶子节点时也就是当节点的左边等于右边时才赋值 
    {                                           //不然地址就错了 ，因为递归调用返回时输入值的地址i就是错的 
        cin >> T[rt].sum;                       //或是赋值为0，
        return;
    }
    create(rt << 1, l, T[rt].mid());  //这个创建进过摸你可以看出如果n为奇数返回的中间值时中间的奇数，则说明创建的时候左边可能比右边的多 
    create(rt << 1 | 1, T[rt].mid()+1, r);  //不能忘记mid（）+1   
    pushup(rt);    //创建完之后别忘了向上传递更新上边的sum值 
}
void Union(int rt, int l, int r, int c)//rt 为根节点，在l和r的范围内部的数都加上c
{
    if (T[rt].left == l&&T[rt].right == r)          //这里就用到lazy做延迟了，这个节点lazy记录的是这个区间内要加的但是不向下进行了， 
    {                                             //就省了时间，sum记录的是这个姐弟啊你左右端点内的所有要加的值的和 
        T[rt].lazy += c;                            
        T[rt].sum += c*(T[rt].right - T[rt].left + 1);  // 
        return;
    }
    if (T[rt].left == T[rt].right) return;
    pushdown(rt, T[rt].right - T[rt].left + 1);
    if (r <= T[rt].mid())           //因为如果为奇数，则返回的中间值时中间的奇数， 
        Union(rt << 1, l, r, c);
    else if (l > T[rt].mid())
        Union(rt << 1 | 1, l, r, c);
    else {
        Union(rt << 1, l, T[rt].mid(), c);
        Union(rt << 1 | 1, T[rt].mid()+1, r, c);
    }
    pushup(rt);    //这个是向上更新，其实就是用下边的两个点来更新这个点
}
int sum(int rt, int l, int r)//求出在某个范围l到r内的和
{
    int ans=0;
    if (T[rt].left == l&&T[rt].right==r)  //看好代码别写错了 
        return T[rt].sum;
    pushdown(rt, T[rt].right - T[rt].left + 1);
    if (r <= T[rt].mid())         /这个必须是小于等于因为 若是奇数则返回的时中间的奇数则就是返回的数比另一半多1，所以就小于等于 
        ans+=sum(rt << 1, l, r);
    else if (l >T[rt].mid())
        ans+=sum(rt << 1 | 1, l, r);
    else {
        ans+=sum(rt << 1, l, T[rt].mid());
        ans+=sum(rt << 1 | 1, T[rt].mid()+1, r);//不要忘记是mid()+1;
    }
    return ans;
}
int main()
{
    int n, m, a, b, c;
    while (cin >> n >> m)
    {
        create(1,1,n);
        while (m--)
        {
            char s;
            cin >> s;
            if (s == 'Q')     //查询在a，b区间的总和 
            {
                cin >> a >> b;
                cout << sum(1, a, b)<<endl;
            }
            else if(s=='B'){      //在  a，b区间内每个节点都加上c 
                cin >> a >> b >> c;
                Union(1, a, b, c);
            }
        }
    }
}
  

 

  
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
  
93
  
94
  
95
  
96
  
97
  
98
 

文章来源: englishcode.blog.csdn.net，作者：知识浅谈，版权归原作者所有，如需转载，请联系作者。

原文链接：englishcode.blog.csdn.net/article/details/80009137