关于指针结构体线段树

P3372 【模板】线段树 1

cengzh @ 2025-01-02 20:21:33

rt，请问是不能用指针结构体来写线段树吗，发现各种操作中会出现串地址的情况，明明build函数外n还等于5，一传进去就变成1了。

# include <stdio.h>
# include <stdlib.h>

int arr[100005];
int n,m;

struct Tree
{
    int l,r;
    long long sum;
    long long tag;
    struct Tree* chi[2];
};

void add_tag(struct Tree* node,int w)
{
    if (node != NULL)
    {
        node->sum += (node->r-node->l+1) * w;
        node->tag += w;
    }
    return ;
}

void push_down(struct Tree* node)
{
    if (!node->tag)
    {
        add_tag(node->chi[0],node->tag);
        add_tag(node->chi[1],node->tag);
        node->tag = 0;
    }
    return ;
}

struct Tree* ini(int l,int r)
{
    struct Tree* tmp = (struct Tree*) malloc (sizeof(struct Tree));
    tmp->chi[0] = tmp->chi[1] = NULL;
    tmp->l = l;
    tmp->r = r;
    tmp->sum = 0;
    return tmp;
}

void push_up(struct Tree* node)
{
    node->sum = node->chi[0]->sum + node->chi[1]->sum;
    return ;
}

void build(struct Tree* node,int l,int r)
{
    printf ("sum:%d l:%d r:%d mid:%d\n",node->sum,l,r,(l+r)/2);
    if (l == r)
    {
        node->sum = arr[l];
        return ;
    }
    exit(-1);
    int mid = (l + r) / 2;

    node->chi[0] = ini(l,mid);
    node->chi[1] = ini(mid+1,r);

    build(node->chi[0],l,mid);
    build(node->chi[1],mid+1,r);

    push_up(node);

    return ;
}

void update(struct Tree* node,int tl,int tr,int w)
{
    if (tl <= node->l && node->r <= tr)
    {
        add_tag(node,w);
        return ;
    }

    push_down(node);

    int mid = (node->l + node->r) / 2;
    long long res=0;

    if (mid >= tl)
    {
        update(node->chi[0],tl,tr,w);
    }
    if (mid < tr)
    {
        update(node->chi[1],tl,tr,w);
    }

    push_up(node);

    return ;
}

long long query(struct Tree* node,int tl,int tr)
{
    if (tl <= node->l && node->r <= tr)
    {
        return node->sum;
    }

    push_down(node);

    int mid = (node->l + node->r) / 2;
    long long res=0;

    if (mid >= tl)
    {
        res += query(node->chi[0],tl,tr);
    }
    if (mid < tr)
    {
        res += query(node->chi[1],tl,tr);
    }

    return res;
}

int main (void)
{
    scanf ("%d %d",&n,&m);

    for (int i=1;i<=n;i++)
    {
        scanf ("%d",&arr[i]);
    }

    struct Tree* root = ini(1,n);

    printf ("%d\n",n);

    build(root,1,n);

 /*   for (int i=0;i<m;i++)
    {
        int opt,x,y;
        scanf ("%d %d %d",&opt,&x,&y);
        if (opt == 1)
        {
            int k;
            scanf ("%d",&k);
            update(root,x,y,k);
        }
        else
        {
            printf ("%lld\n",query(root,x,y));
        }
    }*/
    return 0;
}

by llamn @ 2025-01-02 20:43:49

指针和数组有啥不同，建议来学递归template，在编译期生成结构

by normalpcer @ 2025-01-02 20:46:45

@llamn 你说得对，但他好像在写 C（

by normalpcer @ 2025-01-02 20:55:35

@cengzh

push_down 的条件应为 node->tag。

# include <stdio.h>
# include <stdlib.h>

int arr[100005];
int n,m;

struct Tree
{
    int l,r;
    long long sum;
    long long tag;
    struct Tree* chi[2];
};

void add_tag(struct Tree* node,int w)
{
    if (node != NULL)
    {
        node->sum += (node->r-node->l+1) * w;
        node->tag += w;
    }
    return ;
}

void push_down(struct Tree* node)
{
    if (node->tag)
    {
        add_tag(node->chi[0],node->tag);
        add_tag(node->chi[1],node->tag);
        node->tag = 0;
    }
    return ;
}

struct Tree* ini(int l,int r)
{
    struct Tree* tmp = (struct Tree*) malloc (sizeof(struct Tree));
    tmp->chi[0] = tmp->chi[1] = NULL;
    tmp->l = l;
    tmp->r = r;
    tmp->sum = 0;
    tmp->tag = 0;
    return tmp;
}

void push_up(struct Tree* node)
{
    node->sum = node->chi[0]->sum + node->chi[1]->sum;
    return ;
}

void build(struct Tree* node,int l,int r)
{
    // printf ("sum:%lld l:%d r:%d mid:%d\n",node->sum,l,r,(l+r)/2);
    if (l == r)
    {
        node->sum = arr[l];
        return ;
    }
    // exit(-1);
    int mid = (l + r) / 2;

    node->chi[0] = ini(l,mid);
    node->chi[1] = ini(mid+1,r);

    build(node->chi[0],l,mid);
    build(node->chi[1],mid+1,r);

    push_up(node);

    return ;
}

void update(struct Tree* node,int tl,int tr,int w)
{
    if (tl <= node->l && node->r <= tr)
    {
        add_tag(node,w);
        return ;
    }

    push_down(node);

    int mid = (node->l + node->r) / 2;

    if (mid >= tl)
    {
        update(node->chi[0],tl,tr,w);
    }
    if (mid < tr)
    {
        update(node->chi[1],tl,tr,w);
    }

    push_up(node);

    return ;
}

long long query(struct Tree* node,int tl,int tr)
{
    if (tl <= node->l && node->r <= tr)
    {
        return node->sum;
    }

    push_down(node);

    int mid = (node->l + node->r) / 2;
    long long res=0;

    if (mid >= tl)
    {
        res += query(node->chi[0],tl,tr);
    }
    if (mid < tr)
    {
        res += query(node->chi[1],tl,tr);
    }
    push_up(node);

    return res;
}

void destroy(struct Tree* node) {
    if (node->chi[0])  destroy(node->chi[0]);
    if (node->chi[1])  destroy(node->chi[1]);
    free(node);
}

int main (void)
{
    scanf ("%d %d",&n,&m);

    for (int i=1;i<=n;i++)
    {
        scanf ("%d",&arr[i]);
    }

    struct Tree* root = ini(1,n);

    // printf ("%d\n",n);

    build(root,1,n);

    for (int i=0;i<m;i++)
    {
        int opt,x,y;
        scanf ("%d %d %d",&opt,&x,&y);
        if (opt == 1)
        {
            int k;
            scanf ("%d",&k);
            update(root,x,y,k);
        }
        else
        {
            printf ("%lld\n",query(root,x,y));
        }
    }
    destroy(root);
    return 0;
}

另外，你这个代码会内存泄漏，帮你加了一个 free。通常建议 malloc 一定要配一个 free。

by normalpcer @ 2025-01-02 20:56:26

@cengzh 另外你没有初始化 node->tag。

by Aurie @ 2025-01-02 21:05:19

已改好并 AC。

记录：https://www.luogu.com.cn/record/196875181

代码：

# include <stdio.h>
# include <stdlib.h>

int arr[100005];
int n,m;

struct Tree{

    Tree(int _l,int _r,Tree* ls=nullptr,Tree* rs=nullptr,long long _sum=0,long long _tag=0):l(_l),r(_r),chi({ls,rs}),sum(_sum),tag(_tag){}

    int l,r;
    long long sum;
    long long tag;
    Tree* chi[2];
};

void add_tag(Tree* node,int w){
    if(node){
        node->sum += (node->r-node->l+1) * w;
        node->tag += w;
    }
}

void push_down(Tree* node)
{
    if (node->tag)
    {
        add_tag(node->chi[0],node->tag);
        add_tag(node->chi[1],node->tag);
        node->tag = 0;
    }
    return ;
}

Tree* ini(int l,int r){
    return new Tree(l,r);
}

void push_up(Tree* node){
    node->sum = (node->chi[0]?node->chi[0]->sum:0) + (node->chi[1]?node->chi[1]->sum:0);
}

void build(Tree* &node,int l,int r){
    node = ini(l,r);
    if (l == r)
    {
        node->sum = arr[l];
        return ;
    }

    int mid = (l + r) >> 1;

    build(node->chi[0],l,mid);
    build(node->chi[1],mid+1,r);
    push_up(node);
}

void update(Tree* node,int tl,int tr,int w){
    if (tl <= node->l && node->r <= tr){
        add_tag(node,w);
        return ;
    }

    push_down(node);

    int mid = (node->l + node->r) >> 1;

    if (mid >= tl){
        update(node->chi[0],tl,tr,w);
    }
    if (mid < tr){
        update(node->chi[1],tl,tr,w);
    }

    push_up(node);
}

long long query(Tree* node,int tl,int tr)
{
    if (tl <= node->l && node->r <= tr){
        return node->sum;
    }

    push_down(node);

    int mid = (node->l + node->r) >> 1;
    long long res=0;

    if (mid >= tl)
    {
        res += query(node->chi[0],tl,tr);
    }
    if (mid < tr)
    {
        res += query(node->chi[1],tl,tr);
    }

    return res;
}

int main(){
    scanf ("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf ("%d",&arr[i]);
    }

    Tree* root = nullptr;
    build(root,1,n);
    for(int i=1;i<=m;i++){
        int opt,x,y;
        scanf ("%d%d%d",&opt,&x,&y);
        if (opt == 1){
            int k;
            scanf ("%d",&k);
            update(root,x,y,k);
        }else{
            printf("%lld\n",query(root,x,y));
        }
    }
    return 0;
}

by cengzh @ 2025-01-02 22:35:14

好诶，最近想学动态开点和线段树合并，感觉要用到就学了一下结构体线段树，谢谢大家！已关 @Auroraaaaaa @normalpcer @llamn