suchen

Heim  >  Fragen und Antworten  >  Hauptteil

c++ - 线段树build时出错

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

<code>#include <iostream>

using namespace std;

struct Node

{

    int left;

    int right;

    int delta;

    int sum;

    Node *lc;

    Node *rc;

};

 

void build(Node *cur,int l,int r){

    cur->left=l;

    cur->right=r;

    cur->sum=0;

    if(l+1<r){

        cur->lc = new Node;

        cur->rc = new Node;

        build(cur->lc,l,(l+r)/2);

        build(cur->rc,(l+r)/2,r);

    }

    else cur->lc = cur->rc = NULL;

}

void update(Node *cur){

    cur->lc->sum+=cur->delta*(cur->lc->right - cur->lc->left);

    cur->rc->sum+=cur->delta*(cur->rc->right - cur->rc->left);

    cur->lc->delta+=cur->delta;

    cur->rc->delta+=cur->delta;

    cur->delta=0;

}

void change(Node *cur,int l,int r,int delta){

    if(l<=cur->left&&r>=cur->right){

        cur->sum+=delta*(cur->right - cur->left);

        cur->delta+=delta;

    }

    else{

        if(cur->delta!=0) update(cur);

        if(l<(cur->left+cur->right)/2) change(cur->lc,l,r,delta);

        if(r>(cur->left+cur->right)/2) change(cur->rc,l,r,delta);

        cur->sum=cur->lc->sum+cur->rc->sum;

    }

}

int query(Node *cur,int l,int r){

    if(l<=cur->left&&r>=cur->right)

        return cur->sum;

    else{

        if(cur->delta!=0)

            update(cur);

        int ans=0;

        int t=(cur->left+cur->right)/2;

        if(l<t) ans+=query(cur->lc,l,r);

        if(r>t) ans+=query(cur->rc,l,r);

        return ans;

    }

}

int n,g,m;

int a,b,c,d;

int main(){

    Node *cur;

    cin>>n;

    build(cur,1,n);

    for(int i=1;i<=n;i++){

        cin>>g;

        change(cur,i,i+1,g);

    }

    cin>>m;

    for(int i=1;i<=m;i++){

        cin>>a;

        if(a==1){

            cin>>b>>c>>d;

            change(cur,b,c+1,d);

        }

        else{

            cin>>b>>c;

            cout<<query(cur,b,c+1);

        }

    }

    return 0;

}

</code>

build时出错。
Program received signal SIGSEGV,Segmentation fault.

build的问题已解决,把Node *cur改为Node *cur=new Node就行了
但是change第三次时出错,是wikioi的实例

黄舟黄舟2813 Tage vor579

Antworte allen(3)Ich werde antworten

  • 阿神

    阿神2017-04-17 11:27:39

    已经找到了答案,应当build(cur,1,n+1);

    因为我建的是左闭右开,要存到n就必须到n+1

    Antwort
    0
  • PHPz

    PHPz2017-04-17 11:27:39

    肉眼看了一下,main函数里面cur是一个nullptr,在build函数里面调用cur->left 和 cur->right,肯定段错误。


    楼主搞acm的吧,都开始学习线段树了,也应该学了蛮长时间了,基本的debug还是要学的,你gdb跟一下其实就知道为什么了

    Antwort
    0
  • 黄舟

    黄舟2017-04-17 11:27:39

    可能会int越界,注意用long long

    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

    <code>struct node

    {

        int l,r;

        long long v,lazy;

    }a[600000];

    int b[200003];

    void build(int i,int l,int r)

    {

        a[i].l=l,a[i].r=r,a[i].lazy=0;

        if(l==r)

        {

            a[i].v=b[l];

            return;

        }

        int m=(l+r)/2;

        build(2*i,l,m),build(2*i+1,m+1,r);

        a[i].v=a[2*i].v+a[2*i+1].v;

    }

    void update(int i,int l,int r,long long v)

    {

        a[i].v+=((r-l+1)*v);

        if(a[i].l==l && a[i].r==r)

        {

            a[i].lazy+=v;

            return;

        }

        int m=(a[i].l+a[i].r)/2;

        if(r<=m)

            update(2*i,l,r,v);

        else if(l>m)

            update(2*i+1,l,r,v);

        else

            update(2*i,l,m,v),update(2*i+1,m+1,r,v);

    }

    int query(int i,int l,int r)

    {

        if(a[i].l==l && a[i].r==r)

            return a[i].v;

        int m=(a[i].l+a[i].r)/2;

        if(r<=m)

            return (r-l+1)*a[i].lazy+query(2*i,l,r);

        else if(l>m)

            return (r-l+1)*a[i].lazy+query(2*i+1,l,r);

        else

            return (r-l+1)*a[i].lazy+query(2*i,l,m)+query(2*i+1,m+1,r);

    }

    </code>

    调用的时候build(1,1,n),表示树根下标为1

    Antwort
    0
  • StornierenAntwort