【学习笔记】线段树_线段树modest

线段树用于解决区间问题，此博文只贴模版，题目假设为区间加和区间查询
推荐

1、更新

void pushup(int root){
    tree[root]=tree[root<<1]+tree[root<<1|1];
}
1
2
3

2、建树

void build(int root,int l,int r){
    if (l==r){
        tree[root]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
    pushup(root);
}
1
2
3
4
5
6
7
8
9
10

3、下传lazytag

void pushdown(int root,int l,int r){
    if (tag[root]){
        tag[root<<1]+=tag[root]; tag[root<<1|1]+=tag[root];
        int mid=(l+r)>>1;
        tree[root<<1]+=tag[root]*(mid-l+1); tree[root<<1|1]+=tag[root]*(r-mid);
        tag[root]=0;
    }
}
1
2
3
4
5
6
7
8

4、区间修改（也可用作单点修改）

void update(int root,int l,int r,int L,int R,int delta){
    if (l>R || r<L) return;
    if (l>=L && r<=R){tree[root]+=delta; tag[root]+=delta;}
    pushdown(root,l,r);
    int mid=(l+r)>>1;
    update(root<<1,l,mid,L,R,delta);
    update(root<<1|1,mid+1,r,L,R,delta);
    pushup(root);
}
1
2
3
4
5
6
7
8
9

5、区间查询

int query(int root,int l,int r,int L,int R){
    if (l>R || r<L) return 0;
    if (l>=L && r<=R) return tree[root];
    pushdown(root,l,r);
    int mid=(l+r)>>1;
    int ans=query(root<<1,l,mid,L,R)+query(root<<1|1,mid+1,r,L,R);
    return ans;
}
1
2
3
4
5
6
7
8

LuoGu线段树模板2
Code:

type Node=record
    num,mul,ad:int64;
end;
var
    tree:array[0..1000000] of Node;
    a:array[0..1000000] of int64;
    n,m,p,x,y,z,t:int64;
    i:longint;

procedure build(root,l,r:int64);
var
    mid:int64;

begin
    tree[root].mul:=1;
    if l=r then
    begin
        tree[root].num:=a[l];
        exit;
    end;
    mid:=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1+1,mid+1,r);
    tree[root].num:=(tree[root<<1].num+tree[root<<1+1].num) mod p;
end;

procedure pushdown(root,l,r:int64);
var
    mid:int64;

begin
    mid:=(l+r)>>1;
    tree[root<<1].num:=(tree[root<<1].num*tree[root].mul+tree[root].ad*(mid-l+1)) mod p;
    tree[root<<1+1].num:=(tree[root<<1+1].num*tree[root].mul+tree[root].ad*(r-mid)) mod p;
    tree[root<<1].mul:=tree[root<<1].mul*tree[root].mul mod p;
    tree[root<<1+1].mul:=tree[root<<1+1].mul*tree[root].mul mod p;
    tree[root<<1].ad:=(tree[root<<1].ad*tree[root].mul+tree[root].ad) mod p;
    tree[root<<1+1].ad:=(tree[root<<1+1].ad*tree[root].mul+tree[root].ad) mod p;
    tree[root].mul:=1; tree[root].ad:=0;
end;

procedure multiply(root,tl,tr,l,r,sum:int64);
var
    mid:int64;

begin
    if (tr<l) or (tl>r) then exit;
    if (tl>=l) and (tr<=r) then
    begin
        tree[root].num:=tree[root].num*sum mod p;
        tree[root].mul:=tree[root].mul*sum mod p;
        tree[root].ad:=tree[root].ad*sum mod p;
        exit;
    end;
    pushdown(root,tl,tr);
    mid:=(tl+tr)>>1;
    multiply(root<<1,tl,mid,l,r,sum);
    multiply(root<<1+1,mid+1,tr,l,r,sum);
    tree[root].num:=(tree[root<<1].num+tree[root<<1+1].num) mod p;
end;

procedure add(root,tl,tr,l,r,sum:int64);
var
    mid:int64;

begin
    if (tr<l) or (tl>r) then exit;
    if (tl>=l) and (tr<=r) then
    begin
        tree[root].num:=(tree[root].num+sum*(tr-tl+1)) mod p;
        tree[root].ad:=(tree[root].ad+sum) mod p;
        exit;
    end;
    pushdown(root,tl,tr);
    mid:=(tl+tr)>>1;
    add(root<<1,tl,mid,l,r,sum);
    add(root<<1+1,mid+1,tr,l,r,sum);
    tree[root].num:=(tree[root<<1].num+tree[root<<1+1].num) mod p;
end;

function query(root,tl,tr,l,r:int64):int64;
var
    mid:int64;

begin
    if (tr<l) or (tl>r) then exit(0);
    if (tl>=l) and (tr<=r) then exit(tree[root].num);
    pushdown(root,tl,tr);
    mid:=(tl+tr)>>1;
    exit((query(root<<1,tl,mid,l,r)+query(root<<1+1,mid+1,tr,l,r)) mod p);
end;

begin
    readln(n,m,p);
    for i:=1 to n do read(a[i]);
    build(1,1,n);
    for i:=1 to m do
    begin
        read(t);
        if t=1 then
        begin
            readln(x,y,z);
            multiply(1,1,n,x,y,z);
        end else
        if t=2 then
        begin
            readln(x,y,z);
            add(1,1,n,x,y,z);
        end else
        begin
            readln(x,y);
            writeln(query(1,1,n,x,y));
        end;
    end;
end.
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