# Union of Segments (Basic)(線段樹應用)



- 線段樹主要是可以維持一段區間，所以如果題目是要維持一段區間，可以套線段樹模板
- 如果需要較短時間解題，可以開直接開線段樹陣列，不要用指標，且陣列Size可以開到題目最大輸入資料數4倍，而且不必在Struct Node內設Left和Right參數，因為線段樹往下Search，Parent為i，Left child為2\*i\(node<<1)，Right child: 2\*i+1(node<<1|1)

#define N 200005
struct segment{
    int count,length;
}seg[N<<4];

- 由於已經把segment tree用陣列開出來，且如果要維持的segment不用初始值或是初始值皆為0，就不用build tree
- 使用tag來表示此線段是有被cover以及次數，當tag>=1，表示此線段全部覆蓋，是0，表示沒有完全覆蓋https://blog.csdn.net/malloch/article/details/107999709
- Delete不是要刪去線段數節點，進入update or modify，把tag設定為0，就表示此線段沒有覆蓋到
- 此題題目意思是如果先給4個點在數線上，此時指令沒下4點都是獨立，Report應回傳0

* 當題目表示insert A B，表示把A B點接起來，此時如果Report此線段數是3-1=2

* 此時如果下指令insert A C，則A C整段會包覆住，Report回５－１＝４
* 如果下指令remove A B，由於A C整段會包覆住整段(此節點)，故Report還是5-1=4
:::warning
* 使用分治法，分別往下尋找對應節點modify，終止條件為詢問區間在線段樹區間在ql<=l && qr>=r，此時表示此線段有被覆蓋(詢問區間大於此節點線段數區間)，tag值+1
* !!!條件成立後，繼續程式繼續往下，並持續把值往Root傳，有下列情況要討論:
- tag>=1取該子節點整段(原資料data[r+1]-data[l]，r和l為分治法下的區間值，r+1表示恢復點做計算，e.g. 線段1表示1-2的線段，所以計算時候要改成data[2]-data[1])，所以帶入modify函式時候，區間(ql, qr)要帶入(ql, qr-1)
- tag==0且l\==r表示已經到leaf，length=0
- tag==0但l!=r，取左右子節點的length
- tag一方面也是記錄此線段的cover次數，當為0，表示此段已經沒有被整段cover，需要取該此節點的值(可理解為部分cover，例如1-5 tag為0但其值為2，表示其子節點3-5可能被cover且tag不為0，但是1-2沒有)
- 當tag已經有被標記，其子節點有變化，母節點取值時候依然會取整段區間，且不用下推給leaf (Lazy，需要做才更新)
https://blog.csdn.net/malloch/article/details/107999709
:::
- 只要取root-segment[1]的lenght就知道現在整的區間有多大，segment[0]捨棄不用
- segment本身節點編號以及存的值，不必依照對應的資料陣列或是去存取區間，例如node 2一定要存data[2]或是存1-3資訊，透過2分查找方式，就可以知道其node段應的區間(重要的是查找區間)
* 可用GDB設定斷點除錯 
- 簡介 Debugger 按鈕作用，在上面範例中，我稍微講一下這些按鈕在做啥。
- 第一個按鈕：繼續（Continue），按下去後會持續跑，直到下個中斷點。
- 第二個按鈕：不進入函式（Step over），按下去後，會到在目前這 Function 跑到下一個敘述。
- 第三個按鈕：逐步執行（Step into），按下去後，會進入到每一部 Function 執行敘述並中斷。
- 第四個按鈕：逐步執行（Step out），按下去後，會直接把 Function 執行完並中斷。
- 第五個按鈕：重新起動，重跑 GDB 偵錯。
- 第六個按鈕：停止，停止 GDB 偵錯。
- Ref: https://blog.yangjerry.tw/vscode-cpp-2021-part2/

- 幾何題目可用ggb輔助畫圖幫忙
- https://www.geogebra.org/classic?lang=zh-TW
- 程式碼參考如下(題目原文比較不好懂，多讀幾次)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <tuple>
#define N 200005
using namespace std;

struct segment{
    int count,length; //count->tag, length->interval
}seg[N<<4];//segment tree
vector<int> coords;    // Coordinate mapping
int n;

void update(int node, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        seg[node].count += val;
    } else {
            int mid = (l + r) / 2;
            if (ql <= mid) update(node * 2, l, mid, ql, qr, val);
            if (qr > mid) update(node * 2 + 1, mid + 1, r, ql, qr, val);
    }
        
        if (seg[node].count> 0) {
            seg[node].length = coords[r + 1] - coords[l]; /* Full segment is covered. When we want to get 
                                                            the segment length, r must be plused 1 to the point.*/
        } else if (l == r) {
            seg[node].length = 0;  // Leaf node, no coverage
        } else {
            seg[node].length = seg[node<<1].length + seg[node * 2 + 1].length;
        }
}

void insert(int l, int r) {
    update(1, 0, N, l, r - 1, 1);  // Insert the segment. Since we query the segment, r must be minused 1.
}

void remove(int l, int r) {
    update(1, 0, N, l, r - 1, -1); // Remove the segment. Since we query the segment, r must be minused 1.
}

int query() {
    return seg[1].length;  // Total length of the union of segments. seg[0] is unsed.
}


int main() {
    int n, q;
    cin >> n;
    vector<int> points(n);
    coords.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i];
    }
    
    cin >> q;
    vector<tuple<string, int, int>> queries(q);

    // Read the queries
    for (int i = 0; i < q; ++i) {
        string type;
        int l, r;
        cin >> type;
        if (type != "report") {
            cin >> l >> r;
            --l, --r;  // Convert to 0-based indexing
        }
        queries[i] = {type, l, r};
    }

    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());
    coords=points;

    // Process the queries
    for (auto& _query : queries) {
        string type;
        int l, r;
        tie(type, l, r) = _query;

        if (type == "insert") {
            insert(l, r);
        } else if (type == "delete") {
            remove(l, r);
        } else if (type == "report") {
            cout <<query() << endl;
        }
    }

    return 0;
}

#### Ref: https://cp.wiwiho.me/segment-tree/