`算法知识` 线段树

算法 {(可持久化)线段树SegmentTree}

线段树

定义

性质

算法

代碼模板

namespace ___SegmentTree{
struct __Node_{
public:
    //>> 数据域
    int64_t Sum; @TODO

    //>> 延迟域
    int delay;
    //< 对于任意节点`x`: [[他的数据域是正确的]]<->[[他的所有*祖先节点* 都没有延迟标记]];
    //  . 比如`x`和他的后代 有延迟标记, 这没有问题 此时`x`的数据域是正确的, 只要他的所有*祖先节点*没有延迟;
    //  兒子節點的懶標記 不會用到他, 但他並不是*空的*(即`0`) 因為每一次的懶標記 最終更新到底 都是更新到了兒子節點上為止;

    void Clear_delay(){
        delay = 0;
    }
    bool Check_if_no_delay() const{
        if( delay != 0){ // 这里要与`Clear_delay()`函数的逻辑相对应;
            return false;
        }
        return true;
    }
    friend ostream& operator<<( ostream & _cout, const __Node_ & _a){
        __Debug_list( "Node: {", _a.Sum, _a.delay, "}");
        return _cout;
    }
};

vector<__Node_> __Nodes;
int __Range;
int __Modify_left, __Modify_right, __Query_left, __Query_right;
int64_t __Modify_val;

void __Modify_node( __Node_ & _c, int _length, int64_t _val){
//< 對`_c`節點(其對應的區間長度為`_length`) 執行值為`_val`的修改操作; (該函數的調用場景是 {1(`__Updata_son`):[將一個節點的懶標記 去更新到其2個兒子時], 2(`__Modify`):[直接修改一個節點]};
    //>> 更新*数据域*;
    _c.Sum += (_val * _length); @TODO

    //>> 更新*延迟域*;
    _c.delay += _val;
}
void __Update_son( int _node_id, int _left, int _right){
//< 将当前节点的*延迟* 更新给两个儿子; *当前节点*的数据域一定是*正确的* (不管他没有延迟);
    if( _left == _right){ return;} // 叶子节点没有儿子;
    __Node_ & cur = __Nodes[ _node_id];
    if( cur.Check_if_no_delay()){ return;}

    //>> 用`cur`的*延迟域*, 来更新两个儿子的*{延迟域,数据域}*, 并清空`cur`的*延迟域*;
    __Modify_node( __Nodes[_node_id<<1], ((_left+_right)>>1)-_left+1, cur.delay);
    __Modify_node( __Nodes[_node_id<<1|1], _right-((_left+_right)>>1), cur.delay);

    cur.Clear_delay();
}
void __Update_fa( __Node_ & _fa, const __Node_ & _lson, const __Node_ & _rson, int _lef, int _rig){
//< `lson, rson`的*数据域*一定是正确的, 只需用他俩的*数据域* 来更新 `fa`的*数据域*, 不用管*延迟域*; `[_lef,_rig]`為`_fa`節點的區間;
    _fa.Sum = _lson.Sum + _rson.Sum; @TODO
}
void __Build( int _node_id, int _left, int _right){
    auto & cur = __Nodes[ _node_id];
    cur.Clear_delay();
    
    if( _left == _right){
        cur.Sum = MOD(cur.rawSum) * cur.rawSum; @TODO
        return;
    }
    
    auto mid = (_left + _right)>>1;
    __Build( _node_id<<1, _left, mid);
    __Build( _node_id<<1|1, mid+1, _right);
    __Update_fa( __Nodes[ _node_id], __Nodes[ _node_id<<1], __Nodes[ _node_id<<1|1], (mid-_left+1), (_right - mid));
}
void Initialize( int _range){
    __Nodes.resize( _range * 4);
    __Range = _range;
    __Build( 1, 0, __Range - 1);
}
void __Modify( int _node_id, int _left, int _right){
// 当前节点 他的区间是`[left, right]`;
    if( ( _left >= __Modify_left) && ( _right <= __Modify_right)){
    //>< 当前节点(即`nodes[node_id]`) 他的区间`[left, right]` 是`[modifty_left, modify_right]`的*子区间* (即被包含);
    //   . 當前節點的*數據域*一定是正確的, 其*懶標記*可能並不是空的(即可能已經有懶標記了);
        __Modify_node( __Nodes[ _node_id], _right-_left+1, __Modify_val);
        return;
    }
    __Update_son( _node_id, _left, _right);
    auto mid = (_left+_right)>>1;
    if( (__Modify_left <= mid) && (__Modify_right > mid)){
        __Modify( _node_id<<1, _left, mid);
        __Modify( _node_id<<1|1, mid + 1, _right);
    }
    else if( __Modify_right <= mid){
        __Modify( _node_id<<1, _left, mid);
    }
    else if( __Modify_left > mid){
        __Modify( _node_id<<1|1, mid + 1, _right);
    }
    __Update_fa( __Nodes[ _node_id], __Nodes[ _node_id<<1], __Nodes[ _node_id<<1|1], mid-_left+1, _right-mid);
}
void Modify( int _left, int _right, int64_t _val){
    ASSERT_WEAK_( 0<=_left && _left<=_right && _right<__Range);
    __Modify_val = _val;  __Modify_left = _left;  __Modify_right = _right;
    __Modify( 1, 0, __Range - 1);
}
__Node_ __Query( int _node_id, int _left, int _right){
//< 当前节点 他的区间是`[left, right]`;
    if( (_left >= __Query_left) && (_right <= __Query_right)){
        return __Nodes[ _node_id];
    }
    __Update_son( _node_id, _left, _right);
    auto mid = ( _left + _right) >> 1;
    if( (__Query_left <= mid) && (__Query_right > mid)){
        __Node_ ans;
        auto left = __Query( _node_id<<1, _left, mid);
        auto right = __Query( _node_id<<1|1, mid + 1, _right);
        __Update_fa( ans, left, right, mid-_left+1, _right-mid);
        return ans;
    }
    else if( __Query_right <= mid){
        return __Query( _node_id<<1, _left, mid);
    }
    return __Query( _node_id<<1|1, mid + 1, _right);
}
__Node_ Query( int _left, int _right){
    ASSERT_WEAK_( 0<=_left && _left<=_right && _right<__Range);
    __Query_left = _left;  __Query_right = _right;
    return __Query( 1, 0, __Range-1);
}
void Debug(){
    DE_( "___SegmentTree-Debug-Begin");
    FOR_( i, 0, __Range-1){
        DE_( i, Query(i,i));
    }
    DE_( "___SegmentTree-Debug-End");
}
} // namespace ___SegmentTree
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

維護A[]數組, 進行A[l...r]+=K修改,和A[l]^2+...+A[r]^2查詢

性質

具體見@LINK: https://editor.csdn.net/md/?not_checkout=1&articleId=134148990;

代碼

void __Modify_node( __Node_ & _c, int _length, int64_t _val){
//< 對`_c`節點(其對應的區間長度為`_length`) 執行值為`_val`的修改操作; (該函數的調用場景是 {1(`__Updata_son`):[將一個節點的懶標記 去更新到其2個兒子時], 2(`__Modify`):[直接修改一個節點]};
    //>> 更新*数据域*;
    _c.Sum += (MOD(2) * _val * _c.rawSum);
    _c.Sum += (MOD(_val) * _val * _length);
    _c.rawSum += (_val * _length);

    //>> 更新*延迟域*;
    _c.delay += _val;
}
1
2
3
4
5
6
7
8
9
10

例题

@LINK: https://atcoder.jp/contests/abc322/tasks/abc322_f;
數據域為: pre0, pre1, suf0, suf1, max0, max1 其中pre0為前綴為0的最長長度, suf為後綴, max為任意最長子數組;
懶標記為delay ^= 1;
注意, Build時 如果A[ind] = 1 那麼cur.pre1|suf1|max1 = 1, 但是 千萬別忘記了A[ind]=0的情況 此時你需要更新cur.pre0|suf0|max0 = 1; 別只更新了A[ind]=1的情況 而忘了=0的情況;

@DELI;

AW-4878. 维护数组
. 维护三个值sum, presum, sufsum, sum是原生值, presum需要min( sum, B), sufsum需要min( sum, A);

@Delimiter

LeetCode-6358. 更新数组后处理求和查询
For a Boolean-Array ([0/1, 0/1, ...]), there are two operations:
1 Reverse a interval $[l,r]$;
2 Get the number of 1 in the whole array;

@Delimiter

link
sustain many information (e.g., total sum, maximal prefix sum, maximal suffix sum, maximal sub-interval sum) on each nodes.

link
two operations: (get GCD of a interval) and (add a $val$ on a interval)

link
multi-Delays, one is Add, one is multiplicative-factor.

可持久化線段樹(主席樹)

性質

普通線段樹中 cur的兒子是cur*2, 但是在持久化線段樹裡 他的兒子是Nodes[cur].SonId[?];

對於Git樹的根節點版本, 他的整個樹 你需要給完整的建立出來 (這點與TRIE持久化不同), 因為線段樹會用到update_fa操作 他需要得到兩個兒子的信息, 所以要保證這2個兒子一定不是空的; 這樣就保證了 對於任意一個版本樹 你去遍歷他 不用考慮空節點的情況 他的所有節點 一定是已經開闢了的;

算法

以插入的每一個元素 作為新版本

性質

一個序列A, 第i個版本的線段樹 存儲A[0...i]這些數, 對於區間查詢A[l...r] 就對應為 第r版本的線段樹RT 減去 第l-1版本的線段樹LT, 這裡的減去 是指的RT與LT一一對應的節點信息的相減, 即我們構造一個線段樹T 他的節點x的信息 等於RT的x節點信息減去LT的x節點信息, 那麼會有T等於存儲A[l...r]這些數的線段樹; 當然你要保證 這個節點信息 是符合相減性質的;

@DELI;

代碼

class ___SegmentTree_Persistent{
public:
class __Node_{
public:
    int SonId[ 2]; // `b=SonId[a]`: @IF(`b==-1`):[當前節點的第`a`個兒子暫未開闢], @ELES:[兒子為`Nodes[b]`];
    int Count; // 令當前節點所代表的區間是`[l,r]`, 線段樹裡所有排序在*第[l,...,r]小*的元素 有Count個;
    __Node_(){ Initialize();}
    void Initialize(){ // 一個*空的線段樹* 他只由一個*根節點R*(表示`[0,Range-1]`這個區間) 且R的初始化數據如下;
        memset( SonId, -1, sizeof( SonId));  Count = 0;
    }
    friend ostream& operator<<( ostream & _cout, const __Node_ & _a){
        __Debug_list( _a.SonId, _a.Count, "\n");
        return _cout;
    }
};

int __Range; // 線段樹根節點表示`[0,Range-1]`這個區間;
pair __InsertFlag;  int __InsertData;
int __QueryData;
vector<__Node_> Nodes; // `Nodes[a].SonId[b]=c`: `a`號節點的 第`b`個分支兒子的編號為`c` (如果`c=-1` 說明這個兒子節點還尚未存在);
//< 動態開點 當前已經使用了`[0,...,Nodes.size()-1]`這些節點;
vector VersionRoot; // `VersionRoot[a]=b`: `a`號版本的Trie樹的根節點為`Nodes[b]`;
//< 當前已經有`[0,...,VersionRoot.size()-1]`這些版本;
vector VersionFa; // `VersionFa[a]=b`: `a`號版本的父節點為`b`, 如果`b==-1` 說明`a`版本在Git樹中為*根節點*;
//< `VersionFa.size()=VerionRoot.size()`

void Initialize( int _range, int _nodesEstimateMaximum_, int _versionsEstimateMaximum){
//< `nodesEstimateMaximum`:[預估的總節點個數];  `versionsEstimateMaximum:[預估的總版本個數];
    __Range = _range;
    Nodes.reserve( _nodesEstimateMaximum_);  Nodes.clear();
    VersionRoot.reserve( _versionsEstimateMaximum);  VersionRoot.clear();
    VersionFa.reserve( _versionsEstimateMaximum);  VersionFa.clear();
}
void __Update_fa( __Node_ & _fa, const __Node_ & _lson, const __Node_ & _rson, int _l, int _r){
    _fa.Count = _lson.Count + _rson.Count;
}
void __Create( int _nodeId, int _l, int _r){
    if( _l == _r){
        return;
    }
    Nodes[ _nodeId].SonId[0] = Nodes.size();  Nodes.emplace_back();
    Nodes[ _nodeId].SonId[1] = Nodes.size();  Nodes.emplace_back();
    int mid = (_l + _r) >> 1;
    __Create( Nodes[ _nodeId].SonId[0], _l, mid);
    __Create( Nodes[ _nodeId].SonId[1], mid+1, _r);
    __Update_fa( Nodes[_nodeId], Nodes[Nodes[_nodeId].SonId[0]], Nodes[Nodes[_nodeId].SonId[1]], _l, _r);
}
void Create(){ // 創建一個新的線段樹;
    int rootId = Nodes.size();
    Nodes.emplace_back();
    VersionRoot.push_back( rootId);
    VersionFa.push_back( -1);
    __Create( rootId, 0, __Range-1);
}
void __Insert( int _node_id, int _left, int _right){
//< 当前节点 他的区间是`[left, right]`;
    auto & curNode = Nodes[ _node_id];
    if( _left == _right){
        curNode.Count ++;
        return;
    }
    auto mid = (_left+_right)>>1;
    int son_id = (__InsertData <= mid ? 0 : 1);
    if( __InsertFlag.first == 1){ // 在父版本的基礎上建立新版本
        Nodes.push_back( Nodes[curNode.SonId[son_id]]);  curNode.SonId[ son_id] = (int)Nodes.size() - 1;
    }

    if( son_id == 0){ __Insert( Nodes[_node_id].SonId[son_id], _left, mid);}
    else{ __Insert( Nodes[_node_id].SonId[son_id], mid+1, _right);}

    __Update_fa( Nodes[_node_id], Nodes[Nodes[_node_id].SonId[0]], Nodes[Nodes[_node_id].SonId[1]], _left, _right);
}
void Insert( pair _flag, int _data){
//< @IF(`flag.first=1`):[以`flag.second`號版本為父節點 創建一個新的版本(版本號為`VersionRoot.size()`)];
//  @ELIF(`flag.first==-1`):[直接修改`flag.second`號版本 但要確保*這個版本一定是Git上的葉子節點* 即沒有`VersionFa[?]=flag.second`];
    ASSERT_( IsInInterval_( _data, 0, __Range-1, true));
    __InsertFlag = _flag;  __InsertData = _data;
    int rootId; // 當前所操作的線段樹的根節點;
    if( _flag.first == 1){ // 在父版本的基礎上 創建新版本
        ASSERT_( IsInInterval_( _flag.second, 0, (int)VersionRoot.size()-1, true));
        rootId = Nodes.size();
        Nodes.push_back( Nodes[ VersionRoot[ _flag.second]]); // 複製
        VersionRoot.push_back( rootId);
        VersionFa.push_back( _flag.second);
    }
    else if( _flag.first == -1){ // 在已有版本上進行操作
        ASSERT_( IsInInterval_( _flag.second, 0, (int)VersionRoot.size()-1, true));
        ASSERT_MSG_( "確保不存在`VersionFa[?]==flag.second`, 即該版本是Git上的*葉子節點*;");
        rootId = VersionRoot[ _flag.second];
    }
    else{
        ASSERT_(0);
    }
    __Insert( rootId, 0, __Range-1);
}
int __Query( int _leftNodeId, int _rightNodeId, int _l, int _r){
    if( _l == _r){
        int count = Nodes[_rightNodeId].Count;
        if( _leftNodeId != -1){ count -= Nodes[_leftNodeId].Count;}
        ASSERT_( IsInInterval_( __QueryData, 1, count, true));
        return _l;
    }
    
    int count = Nodes[Nodes[_rightNodeId].SonId[0]].Count;
    if( _leftNodeId != -1){ count -= Nodes[Nodes[_leftNodeId].SonId[0]].Count;}
    //< `T`的定義為`@LINK: Query函數裡的定義`, 此時count表示線段樹`T`的 `[l,r]`區間所對應的節點的 *左兒子的信息*;

    int son_id = ?;
    
    int newLeftId = -1;
    if( _leftNodeId != -1){ newLeftId = Nodes[_leftNodeId].SonId[son_id];}

    int mid = (_l + _r)>>1;
    if( son_id == 0){ return __Query( newLeftId, Nodes[_rightNodeId].SonId[son_id], _l, mid);}
    return __Query( newLeftId, Nodes[_rightNodeId].SonId[son_id], mid+1, _r);
}
int Query( int _lv, int _rv, int _data){
//< `T`的定義為 以(`[_lv+1,...,_rv]`這些版本新增加的數)來構造出的線段樹(這是虛擬的), 此時就是在`T`這個虛擬線段樹上 對`data`進行查詢;
//  . 確保`lv`在Git樹中一定是`rv`的*祖節點*, 令`lv`版本的TRIE樹所對應的字符串集合為`SL` 令`rv`版本對應的字符串集合為`SR`, 則`T`等於差集`SR/SL`];
//    . 注意 這裡的`lv,rv` 和前綴和思想很像 但有一點不同, 這裡是不包含`lv`的 即實際上你查詢的是`[lv+1, ..., rv]`這個區間 (即這些`(lv,rv]`版本所調用的修改操作);
    ASSERT_( _lv>=-1 && _lv<=_rv && _rv>=0 && _rv<(int)VersionRoot.size());
    __QueryData = _data;
    int rightId = VersionRoot[ _rv];
    int leftId;
    if( _lv == -1){
        leftId = -1;
    }
    else{
        ASSERT_MSG_( "確保`lv`在Git樹中一定是`rv`的*祖節點*");
        leftId = VersionRoot[ _lv];
    }
    return __Query( leftId, rightId, 0, __Range-1);
}
friend ostream& operator<<( ostream & _cout, const ___SegmentTree_Persistent & _tr){
    __Debug_list( "*SegmentTree-Debug-Begin* \n");
    __Debug_list( _tr.VersionRoot, _tr.VersionFa, "\n");
    FOR_( v, 0, (int)_tr.VersionRoot.size()-1){
        function dfs = [&]( int _curId, int _l, int _r){
            __Debug_list( _l, _r, _tr.Nodes[_curId]);
            if( _l == _r){
                return;
            }
            int mid = (_l+_r)>>1;
            dfs( _tr.Nodes[_curId].SonId[0], _l, mid);
            dfs( _tr.Nodes[_curId].SonId[1], mid+1, _r);
        };
        __Debug_list( "Version(" + to_string(v) + ")-Begin", "\n");
        dfs( _tr.VersionRoot[ v], 0, _tr.__Range-1);
        __Debug_list( "Version(" + to_string(v) + ")-End", "\n");
    }
    __Debug_list( "*SegmentTree-Debug-End* \n");
    return _cout;
}
}; // class ___SegmentTree_Persistent

FOR_(i, 0, N-1){
    if( i == 0){
        Tr.Create();
        Tr.Insert( {-1,0}, ?);
    }
    else{
	    Tr.Insert( {1,i-1}, ?);
    }
}
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

例題

求某個區間裡的第K大數 @LINK: https://editor.csdn.net/md/?not_checkout=1&articleId=134083948;

筆記

#Multi Delays#
When there are multiple Delays on a node, when it update_son, the order of the Delays when taking these Delays to update its sons is vital.
More Details

@DELI;

#The update_son operation in $Modify$#

void modify_1( int _node_id, int _left, int _right){
    if( ( _left >= modify_1_left) && ( _right <= modify_1_right)){ //< Target-Interval contains the current whole segment.
        @Pos_0
        return;
    }
    update_son( _node_id, _left, _right);
    ...
}   
1
2
3
4
5
6
7
8

These two section can be swapped, it is still correct.

• If update_son is first, then it means that when we at @Pos_0, the Delay of current-node is empty, so, the new Delay value can be relatively easy to calculate.
  But, it costs more times, because if we at @Pos_0, we can also do correct process without the operation of update_son.
• If update-son is not the first (as above), it means when we at @Pos_0, the Delay of current-node maybe not empty.

Whichever the case, the $value$ of current-node are same, the only difference is whether Delay of current-node is empty.

---

@DELI;

#A special case#
We have a array $A$ $[1,2,3,...]$, they are all zeros initially, there are two operations:

• interval-modify, $[l,r]+=k$, (k may be negative)
• whole-array-query, $\sum _{i=1}^n(A[i]>0?1:0)$

Because the interval-modify, so the Delay for $k$ is needed, the information of a node:

• answer (corresponding to the query above), it equals to $lson.answer+rson.answer$.
• value (for a leaf node, it denotes $k$ according to mentioned above), but what’s the meaning for a non-leaf node?
• Delay-value

Discuss the $value$ of a non-leaf node (suppose a operation $modify(l,r,k)$ and a non-leaf node $c$ is contained by $[l,r]$:

• if it is defined to $lson.value+rson.value$, when DFS-Modify at $c$, the $value$ of $c$ can be updated correctly, but the $answer$ of $c$ can’t be updated by $k$ correctly.
• If it is defined to $min(lson.value,rson.value)$, when DFS-Modify at $c$, the $value$ of $c$ can be updated correctly, for $answer$ of $c$. it still can’t be derived by $k$ correctly.
  … if the updated $value$ of $c$ is $>0$, then $answer$ equals to the length of the segment of $c$.
  … but, if the updated $value$ of $c$ if $\le 0$, the correct $answer$ is not solvable by the original $answer$ and $k$.

In summary, there is no clear relation (formula) between $answer$ and $k$ of a non-leaf node ($k$ is the interval-modify acted on this node)

@DELI;

#Interval-modify#

When Modify, for a non-leaf node $c$ which is contained by the target-modify-interval, then DFS will return at this node without visiting its sons.
Then, the information of $c$ will be updated by $modif{y}_{val}$ and the Delay of $c$ will be added by $modif{y}_{val}$.

Because, here the information of $c$ is updated by $modif{y}_{val}$, not by its two sons, so you must ensure this process is feasible.
(Traditionally, the information of any non-leaf node only depends on its two sons, but here it is not)
More details

@DELI;

#Delay-Version#
Traditional, we know that the information of a node equals to (or depends on) the information of its $Lson$ and $Rson$.
But, in the Delay-Version, it is not always the case.

When Modify, for a node $c$ which is contained by the target-modify-interval, then DFS will return at this node without visiting its sons.
So, the information of $c$ will be updated by $modif{y}_{val}$ (make sure the information of $c$ is absolutely correct), and the delay-flag of $c$ will by added by $modif{y}_{val}$.
As a result, the information of any node that is a (grand)son of $c$ is wrong (due to there has a delay-flag of $c$), on the other hand, the information of $c$ not equals to the information of its two sons.

The information of a node is correct, if and only if, any of its (grand)father node has no Delay.

---

Another property of Delay is, suppose there is a Delay at node $c$ (that means the information of any node which is a (grand)son of $c$ is wrong).
Now, we locate at $c$ and are going to visit to $lson$ (the left-son of $c$) (the DFS may be Modify, or Query, anyway), we need to perform the operation $updat{e}_{s}on$ to deliver the Delay of $c$ to updating its two sons (make sure the information of its two sons is correct when we visit it)
So, we need use the Delay of $c$ to update the information of $lson$. Therefore, you must ensure that the information of a $lson$ (i.e., a interval) can be updated by a $modif{y}_{val}$ (Delay means the $modif{y}_{val}$ essentially), not by its two sons (because the information of its two sons is wrong)
More details

@DELI;

#The nature of $Modify\&Query$#
For a target interval $[l,r]$ (either Modify or Query), it will divided into several sub-intervals according to the structure of this Segment-Tree.
Assuming it divided into $[l,a][a+1,b][b+1,r]$, each of these sub-intervals corresponds to a unique $id$
Let’s call these $3$ $id$s be the set $i{d}_{cur}$, and the set of the $id$ of all $ancestor$s of $i{d}_{cur}$ be $i{d}_{fa}$

$i{d}_{cur}$ and $i{d}_{fa}$ are the nodes that $DFS$ visited.

@DELI;

#根节点必须是1#
线段树的各个节点, 就对应: (数组下标); 根节点, 不可以使用0下标!!!
这会导致, 他的左儿子的下标是0 * 2 = 0!!!

所以, 根必须是1

@DELI;

#区间范围#
线段树所维护的区间, 可以包含负数, 比如, 要维护的区间是: [L, R],
则: 线段树的总节点个数是$M=(R-L+1)\ast 3$, 也就对应线段树数组的下标 Tree tr[ M];
即, 所有节点的下标是: $[0,M]$范围

但是, 这并不是说明, [L, R]的范围是[0, M]范围; 这是两个不同的概念

比如, [L, R]是: [-10, -2]

@DELI;

#下取整#
因为会涉及负数, 和二分一样, 要考虑(下取整)问题;

将[l, r], 令$mid=(l+r)divide2$, 分成了: [l, mid] 和 [mid+1, r]
… 那么, 如果[l,r]不是叶子节点, 就必须要保证: [l, mid]或[mid+1, r], 不会和[l, r]一样; 否则就死循环了;

比如: [-5, -6]; 如果用向0取整 $mid=-11/2=-6$, 那么会变成[-5, -6] [-7, -6], 可以发现, 死循环了!

因此, 要用: $mid=(l+r)>>1$ 严格向下取整;

@DELI;

#线段树#
给定一个区间[L, R] (可以涉及负数), 要频繁的(查询/修改) 其中某个(连续的子区间)

线段树是对于一个区间, 分成了: 若干个子区间;
$比如[3,10],是分成为:[3,3][4,7][7,10]$

即, 转换为了: (非重复覆盖问题); 而因为可重复覆盖问题, 一定可以转换为: 非重复覆盖问题; 因此, 这两类 都能用线段树;

@DELI;

#DFS sub-Tree#
Every interval [L, R] (whatever Query or Modify), corresponding to a DFS sub-Tree.

[--------] (1)
[----]      [----] (2,3)
[--]   [--]  [--]   -- (4,5,6,7)
- {[-]  - -   - -} - - (8,9,10,11,12,13,14,15)

the [] segments means the path of DFS, the {} means the target interval. (index starts with 1)
1
2
3
4
5
6

The interval {-----} [2,6], corresponds to the sub-Tree {1,2,3,4,5,6,9}.

For a given target interval [L, R] (whatever for Query or Modify), DFS would only visit those nodes which is intersect the target interval [L, R] (and its father node is not totally within [L, R], if so, then the DFS will return at the father node without visiting its son-nodes) – That is a pivotal property in Segment-Tree

The leaves of this sub-Tree {9, 5, 6}, exactly corresponding to the target interval [L=2, R=6] ([2, 2]–the segment of 9-node, [3, 4]–the segment of 5-node, [5, 6]–the segment of 6-node). So you need to merge the information of those leaves {9, 5, 6}. For instance, at the node-2, you should return the information which merges the information of node-9 and node-5 (note, the information returned by node-2 differs from the information of node-2 stored by the Segment-Tree. More precisely, the information of the former means the interval [2,3,4], the information of the latter means the interval [1,2,3,4])

---

We classify these visited nodes by DFS (i.e., the nodes of DFS sub-Tree), assuming $c$ is one visited node, $l,r$ be its sons, and the target interval is [L, R]. For a visited node $c$ (the segment of $c$ is intersected with [L, R]):

• Being totally contained (such nodes like {9, 5, 6}), return the information of this node (the information is being sustained by the Segment-Tree), i.e. return node[ c] it contains all the information in this segment.

• Only intersect right-son (such nodes like {4}), proceeding return what is returned by DFS, that is return DFS( r). (Note, DFS( r) is not necessary equal to node[ r], because $r$ may be partially intersected or total contained (it is true for the latter), next section will be explained in detail)

• Only intersect left-son (such nodes like {3}) return DFS( l);

• Intersect both left-right son, but not being totally contained (such nodes like {1, 2})

  --------    (c)
  -[--- ----] (l,r)
  
  [] means the target interval [L,R]
  1
  2
  3
  4

  And we have auto ll = DFS( l), rr = DFS( r).
  There is a very crucial property, due to the target interval [L,R] is a interval, the intersection between [L,R] and $l$ must be a suffix of $l$, the same as $r$ must be a prefix of $r$. That means the union of the prefix and suffix is a consecutive interval in $c$.

  There will never has a case in which the intersection of [L,R] and $l$ is not a suffix of $l$ and the intersection of [L,R] and $r$ is not a prefix of $r$.

  so, we let $ll$ be the information of the intersection of [L,R] and $l$ (just like the Segment-Tree, as we know, the information of $l$ means the information of its segment, but now $ll$ means the information of the suffix of its segment), $rr$ be the information of the intersection of [L, R] and $r$. And then merge $ll,rr$ just like the update_fa operation of Segment-Tree.

  So, the Query-function has a return $Node$, Node v = DFS( c) it means the information of the intersection of node-$c$ and the target interval [L, R] is evaluated to $v$.

@DELI;

#区间判断#
线段树的核心, 就是(区间)的修改和查询 (如果是单点, 可以转换为长度为1的区间)

比如cur为当前遍历的线段树节点的区间, tar为要操作的区间; (且, 此时保证: tar和cur一定是相交的, 即有)
TODO

@DELI;

#节点个数#
假如区间范围是[L, R] (可以有负数), 即区间长是: M = R-L+1; 即叶子节点有M个

那么, 线段树的节点数, 可不是(M * 2); … 如果这么想, 是把线段树当成是: 完全二叉树了…

线段树虽然是二叉树, 但并不是完全二叉树;

区间长是M, 他最多分Log2(M) + 1次, 可以到达叶子节点; (比如对于[1, 100]区间, 要达到叶子节点, 要走7步; 而log2(100) = 6)
即数的高度是(Log2(M) + 2) … 要包括根节点;
那么, 一个高度为h的树, 最多有$2^h-1$个节点; 即$M\ast 4$个节点