Segment tree HELP!

https://codeforces.com/contest/339/problem/D
The above is the link to the problem, I am having some issues with the code lately(RE) and it just wont seem to work. Below is what I have done:

Do you know how big your variable “big” is?

1 Like

Quite big haha, but then how do i store size of 4*n which is required for segment tree, bear me because I am new to this topic.

4 * (1<<17) should be fine.

1 Like

Well why do you need 1 << 30 when the maximum N is just 17 :slight_smile:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void build_tree(ll tree[],ll ar[],ll v,ll tl,ll tr,ll temp)
{
if(tl==tr)
{
tree[v] = ar[tl];
return;
}
ll tm = (tl+tr)/2;
build_tree(tree,ar,2v,tl,tm,(temp+1)%2);
build_tree(tree,ar,2
v+1,tm+1,tr,(temp+1)%2);
if(temp==1)
tree[v] = tree[2v]|tree[2v+1];
else
tree[v] = tree[2v]^tree[2v+1];
}
void update_tree(ll tree[],ll ar[],ll tl,ll tr,ll v,ll pos,ll value,ll temp)
{
if(tl==tr)
{
tree[v] = value;
return;
}
ll tm = (tl+tr)/2;
if(pos<=tm)
update_tree(tree,ar,tl,tm,2v,pos,value,(temp+1)%2);
else
update_tree(tree,ar,tm+1,tr,2
v+1,pos,value,(temp+1)%2);
if(temp==1)
tree[v] = tree[2v]|tree[2v+1];
else
tree[v] = tree[2v]^tree[2v+1];
}
int main()
{
ll n,m;
cin >> n >> m;
ll temp = pow(2,n);
ll ar[temp];
for(ll i=0;i<temp;i++)
{
cin >> ar[i];
}
ll tree[2temp];
build_tree(tree,ar,1,0,temp-1,n%2);
//for(int i=1;i<2
temp;i++)
// cout << tree[i] << " ";
while(m–)
{
ll a,b;
cin >> a >> b;
update_tree(tree,ar,0,temp-1,1,a-1,b,n%2);
cout << tree[1] << “\n”;
}
return 0;
}

This is my implementation of this problem. I made tree according to required size.

https://codeforces.com/contest/339/submission/62583742

Yes sorry, sitting for 4 hours straight has its own charms.

1 Like

Thank you appreciate the help.

1 Like

No problem. Good luck with this.

2 Likes