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
#include<iostream>
using namespace std;
struct SegNode
{
    int leftBound, rightBound;
    int sum;
    int lazyTag_set, lazyTag_add;
    SegNode *left, *right;
};
SegNode* Seg_build(int *Val, int leftBound, int rightBound)
{
    SegNode *root = new SegNode;
    root->leftBound = leftBound;
    root->rightBound = rightBound;
    root->lazyTag_set = -1;
    root->lazyTag_add = 0;
    root->left = root->right = NULL;
    if(leftBound == rightBound)
        root->sum = Val[root->leftBound];
    else
    {
        int mid = (leftBound + rightBound) / 2;
        root->left = Seg_build(Val, leftBound, mid);
        root->right = Seg_build(Val, mid+1, rightBound);
        root->sum = root->left->sum + root->right->sum;
    }
    return root;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX