elements revert to 0 after running functions

Question

I was writing this task https://codeforces.com/contest/459/problem/D on codeforces and my solution uses trees, but after running update function every element goes back to 0.

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000009],ans1[1000009],ans2[1000009],fans,w;
map<int,int> pref;

struct Node{
    Node *L,*R;
    int Sum;
    Node()
    {
        Sum=0;
        L=NULL;
        R=NULL;
    }
}*root = new Node();

void update(Node *it,int l,int r,int q)
{
    if(it==NULL) it = new Node();
    if(q<l || q>r) return;
    it->Sum ++;
    cout<<l<<" "<<r<<" "<<q<<" "<<it->Sum<<endl;
    if(l==r) return;
    update(it->L,l,(l+r)/2,q);
    update(it->R,(l+r)/2+1,r,q);
    
}

void findans(Node *it,int l,int r,int L,int R)
{
    if(it==NULL) 
    {
        it = new Node();
        cout<<"1 ";
    }
    cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<it->Sum<<endl;
    if(l>=L && r<=R) w+=it->Sum;
    if(l!=r) if(l<=R && r>=L)
    {
        findans(it->L,l,(l+r)/2,L,R);
        findans(it->R,(l+r)/2+1,r,L,R);
    }
}
int main()
{
    cin>>n;
    for(k=1;k<=n;k++)
    {
        cin>>a[k];
        pref[a[k]]++;
        ans1[k]=pref[a[k]];
    }
    
    pref.clear();
    for(k=n;k>=1;k--)
    {
        pref[a[k]]++;
        ans2[k]=pref[a[k]];
    }
    
    for(k=n;k>=1;k--)
    {
        w=0;
        findans(root,1,n,1,ans1[k]-1);
        fans+=w;
        update(root,1,n,ans2[k]);
        cout<<endl;
    }
    cout<<fans;
}

this is the code(I have extra couts so I could find out where was the problem). also root gets updated normally but every other nodes -> sum goes back to 0 ( sorry for my bad english )

The creation of the new nodes is not propagated back to the caller. I think you meant to do this: `void findans(Node *&it,int l,int r,int L,int R)` — , Aug 06 '21 at 12:35
@Frank yes it worked thank you very much kind stranger. sorry for dumb question lol — giorgigiorgi, Aug 06 '21 at 12:37
Here's some mandatory reading: [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Ted Lyngmo, Aug 06 '21 at 12:42

score 1 · Answer 1 · answered Aug 06 '21 at 12:38

if(it==NULL) it = new Node();

it itself is a local variable, so any changes to it will only be scoped to the function. In other words, calling findans(x, ...) will leave x in the same state it was prior to calling the function.

To fix this, change findans() to accept a reference to a pointer:

void update(Node *&it,int l,int r,int q)
{
...
}

elements revert to 0 after running functions

1 Answers1