线段树

拖了好久了呀，终于是把线段树写了，这个实在太好用了，经常能用

原理就先不写了，听了好多遍了，都大概懂了，一写代码还是很容易理解

就先放上来吧，当作模板看一下

P3372：

区间求和，区间修改

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
/* ---------------------------------------------------------------------------------------------*/
struct Tree
{
    int l,r;
    ll sum,lazy;
}tree[4*MAX];
int a[MAX];
/* ---------------------------------------------------------------------------------------------*/

void bulid(int pos,int l,int r)
{
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r)
    {
        tree[pos].sum = a[l];
        return;
    }
    int mid = (l+r)>>1;
    bulid(pos<<1,l,mid);
    bulid(pos<<1|1,mid+1,r);
    tree[pos].sum = tree[pos<<1].sum + tree[pos<<1|1].sum;
}

void pushdown(int pos)
{
    if(tree[pos].lazy)
    {
        tree[pos<<1].sum += tree[pos].lazy*(tree[pos<<1].r - tree[pos<<1].l + 1);
        tree[pos<<1|1].sum += tree[pos].lazy*(tree[pos<<1|1].r - tree[pos<<1|1].l + 1);
        tree[pos<<1].lazy += tree[pos].lazy;
        tree[pos<<1|1].lazy += tree[pos].lazy;
        tree[pos].lazy = 0;

    }
}

void update(int pos,int l,int r,int x)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        tree[pos].sum += (ll)x * (tree[pos].r - tree[pos].l + 1);
        tree[pos].lazy += x;
        return;
    }
    pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) update(pos<<1,l,r,x);
    if(r > mid) update(pos<<1|1,l,r,x);
    tree[pos].sum = tree[pos<<1].sum + tree[pos<<1|1].sum;
}

ll query(int pos,int l,int r)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        return tree[pos].sum;
    }
    pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    ll ans = 0;
    if(l <= mid) ans += query(pos<<1,l,r);
    if(r > mid) ans += query(pos<<1|1,l,r);
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N >> M;
    for(int i = 1;i <= N;i++)
    {
        cin >> a[i];
    }
    bulid(1,1,N);
    int x,y,z;
    while(M--)
    {
        cin >> x;
        if(x == 1)
        {
            cin >> x >> y >> z;
            update(1,x,y,z);
        }
        else
        {
            cin >> x >> y;
            cout << query(1,x,y) <<endl;
        }
    }
    return 0;
}

P3373

同样是区间修改，区间求和

但是修改方式分为加法，和乘法

lazy标记涉及到加法与乘法的优先问题

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
/*---------------------------------------------------------------------------------------------------*/
//线段树
struct Tree
{
    int l,r;
    ll sum;
    ll lazyadd,lazymul;
}tree[4*MAX];
int a[MAX];
int P;
/* --------------------------------------------------------------------------------------------------*/

void bulid(int pos,int l,int r)
{
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r)
    {
        tree[pos].sum = a[l];
        tree[pos].lazymul = 1;
        return;
    }
    int mid = (l+r)>>1;
    bulid(pos<<1,l,mid);
    bulid(pos<<1|1,mid+1,r);
    tree[pos].sum = tree[pos<<1].sum + tree[pos<<1|1].sum;
    tree[pos].lazymul = 1;
}

void pushdown(int pos)
{
    tree[pos<<1].sum = (tree[pos<<1].sum * tree[pos].lazymul) % P;
    tree[pos<<1|1].sum = (tree[pos<<1|1].sum * tree[pos].lazymul) % P;
    tree[pos<<1].sum = (tree[pos<<1].sum + tree[pos].lazyadd*(tree[pos<<1].r - tree[pos<<1].l + 1)) % P;
    tree[pos<<1|1].sum = (tree[pos<<1|1].sum + tree[pos].lazyadd*(tree[pos<<1|1].r - tree[pos<<1|1].l + 1)) % P;

    tree[pos<<1].lazyadd = (tree[pos<<1].lazyadd*tree[pos].lazymul) % P;
    tree[pos<<1|1].lazyadd = (tree[pos<<1|1].lazyadd*tree[pos].lazymul) % P;
    tree[pos<<1].lazymul = (tree[pos<<1].lazymul*tree[pos].lazymul) % P;
    tree[pos<<1|1].lazymul = (tree[pos<<1|1].lazymul*tree[pos].lazymul) % P;
    tree[pos<<1].lazyadd = (tree[pos<<1].lazyadd + tree[pos].lazyadd ) % P;
    tree[pos<<1|1].lazyadd = (tree[pos<<1|1].lazyadd + tree[pos].lazyadd ) % P;

    tree[pos].lazyadd = 0;
    tree[pos].lazymul = 1;
}

void updateadd(int pos,int l,int r,int x)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        tree[pos].sum = (tree[pos].sum + (ll)x * (tree[pos].r - tree[pos].l + 1)) % P;
        tree[pos].lazyadd = (tree[pos].lazyadd + x) % P;
        return;
    }
    if(tree[pos].lazyadd || tree[pos].lazymul != 1) pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) updateadd(pos<<1,l,r,x);
    if(r > mid) updateadd(pos<<1|1,l,r,x);
    tree[pos].sum = (tree[pos<<1].sum + tree[pos<<1|1].sum) % P;
}

void updatemult(int pos,int l,int r,int x)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        tree[pos].sum = ((ll)x * tree[pos].sum) % P;
        tree[pos].lazymul = (tree[pos].lazymul*x) % P;
        tree[pos].lazyadd = (tree[pos].lazyadd*x) % P;
        return;
    }
    if(tree[pos].lazyadd || tree[pos].lazymul != 1) pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) updatemult(pos<<1,l,r,x);
    if(r > mid) updatemult(pos<<1|1,l,r,x);
    tree[pos].sum = (tree[pos<<1].sum + tree[pos<<1|1].sum) % P;
}

ll query(int pos,int l,int r)
{
    if(l <= tree[pos].l && r >= tree[pos].r)
    {
        return tree[pos].sum;
    }
    if(tree[pos].lazyadd || tree[pos].lazymul != 1) pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    ll ans = 0;
    if(l <= mid) ans += query(pos<<1,l,r);
    ans %= P;
    if(r > mid) ans += query(pos<<1|1,l,r);
    ans %= P;
    return ans;
}


int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N >> M >> P;
    for(int i = 1;i <= N;i++)
    {
        cin >> a[i];
    }
    bulid(1,1,N);
    int x,y,z;
    while(M--)
    {
        cin >> x;
        if(x == 1)
        {
            cin >> x >> y >> z;
            updatemult(1,x,y,z);
        }
        else if(x == 2)
        {
            cin >> x >> y >> z;
            updateadd(1,x,y,z);
        }
        else if(x == 3)
        {
            cin >> x >> y;
            cout << query(1,x,y) <<endl;
        }
    }
    return 0;
}

HUD1752

单点更新

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
/*---------------------------------------------------------------------------------------------------*/
//线段树
struct Tree
{
    int l,r;
    ll sum,lazy;
    int mx;
}tree[4*MAX];
int a[MAX];
/* --------------------------------------------------------------------------------------------------*/

void bulid(int pos,int l,int r)//建树
{
    tree[pos].l = l;
    tree[pos].r = r;
    if(l == r)
    {
        tree[pos].mx = a[l];
        return;
    }
    int mid = (l+r)>>1;
    bulid(pos<<1,l,mid);
    bulid(pos<<1|1,mid+1,r);
    tree[pos].mx = max(tree[pos<<1].mx,tree[pos<<1|1].mx);
}

void update(int pos,int v,int x)
{
    if(tree[pos].l == v && tree[pos].r == v)
    {
        tree[pos].mx = max(tree[pos].mx,x);
        return;
    }
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(v <= mid) update(pos<<1,v,x);
    if(v > mid) update(pos<<1|1,v,x);
    tree[pos].mx = max(tree[pos<<1].mx,tree[pos<<1|1].mx);
}

int query(int pos,int l,int r)
{
    if(tree[pos].l >= l && tree[pos].r <= r)
    {
        return tree[pos].mx;
    }
    int ans = 0;
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if(l <= mid) ans =max(query(pos<<1,l,r),ans);
    if(r > mid) ans =max(query(pos<<1|1,l,r),ans);
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    while(cin >> N >> M)
    {
        for(int i = 1;i <= N;i++)
        {
            cin >> a[i];
        }
        bulid(1,1,N);
        int x,y;
        char c;
        while(M--)
        {
            cin >> c;
            if(c == 'U')
            {
                cin >> x >> y;
                update(1,x,y);
            }
            else
            {
                cin >> x >> y;
                cout << query(1,x,y) <<endl;
            }
        }
    }

    return 0;
}