segment_tree/tree1.cpp at master · 5133n/segment_tree · GitHub

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
//
//https://e-maxx.ru/algo/segment_tree#24
//

#include <iostream>
#include <vector>
#include <map>
using namespace std;

#define MAX_SHARE 1000
#define TREE_SIZE MAX_SHARE * 2 * 4

class SegTree
{
private:
    vector<int> tree;
    //int tree[TREE_SIZE];
    int n = 0;

private:
    void build(vector<int> a, int v, int l, int r)
    {
        if (l == r)
        {
            tree[v] = a[l];
        }
        else
        {
            int m = (l + r) / 2;
            build(a, v * 2, l, m);
            build(a, v * 2 + 1, m + 1, r);
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }

    int sum(int v, int tl, int tr, int l, int r)
    {
        if (l > r)
        {
            return 0;
            //throw std::invalid_argument("l > r");
        }
        if (l == tl && r == tr)
        {
            return tree[v];
        }
        int m = (tl + tr) / 2;
        return sum(v * 2, tl, m, l, min(r, m)) + sum(v * 2 + 1, m + 1, tr, max(l, m + 1), r);
    }

    void update(int v, int l, int r, int pos, int new_value)
    {
        if (l == r)
        {
            tree[v] = new_value;
        }
        else
        {
            int m = (l + r) / 2;
            if (pos <= m)
            {
                update(v * 2, l, m, pos, new_value);
            }
            else
            {
                update(v * 2 + 1, m + 1, r, pos, new_value);
            }
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }

public:
    void init(vector<int> &a)
    {
        tree.resize(TREE_SIZE, 0);
        build(a, 1, 0, a.size() - 1);
        n = a.size();
    }

    int get_sum(int l, int r)
    {
        return sum(1, 0, n - 1, l, r);
    }

    void change(int pos, int new_value)
    {
        cout << n << " " << pos << endl;
        update(1, 0, n - 1, pos, new_value);
    }

    void add(int value)
    {
        //cout << "n: " << n << endl;
        ++n;
        update(1, 0, n - 1, n, value);
        //n++;

    }
};

int main()
{
    SegTree tree;
    vector<int> a = {1, 2, 3, 4, 6, 7};
    tree.init(a);
    cout << tree.get_sum(1, 5) << endl;
    tree.change(3, 1000);
    cout << tree.get_sum(1, 5) << endl;
    //tree.add(10000);
    tree.change(5, 8);
    cout << tree.get_sum(1, 6) << endl;
    // tree.change(6, 1);
    //tree.change(6, 1);
    tree.add(1);
    cout << tree.get_sum(1, 6) << endl;
    cout << endl;
}