Segment Trees #7 Xenia and Bit Operations

D. Xenia and Bit Operations

Problem Statement: here

Solution: [EASY BUT DIFFERENT] 

This construction of segment trees is non-trivial.

So, as we have been told, each leaf will store the value of the array. But, remember, as what we always do to build our segment tree is perform the same nature of operation, like take max of child, or min or sum or diff or etc, here we need to check about the parity of depth. Based on parity. we will take either xor/or of their children. We know, the depth of our tree is n, because there are exactly 2^n leaf nodes. If we are at any depth d in our tree, nodes in this depth will be xor of children if the parity of n and d are same else we will take or.

The Code:

ll n,m; ll a[(1<<18) + 1]; ll seg[4*(1<<18) + 5]; void push(ll ind){ ll depth = (ll)log2(ind); if ((depth^n)&1) seg[ind] = seg[2*ind]|seg[2*ind+1]; else seg[ind] = seg[2*ind]^seg[2*ind+1]; } void build(ll ind, ll l, ll r){ if (l == r){ seg[ind] = a[l]; return; } ll mid = (l+r)/2; build(2*ind,l,mid); build(2*ind+1,mid+1,r); push(ind); } void update(ll ind, ll l, ll r , ll t, ll val){ if (t < l || t > r){ return; } if (l == r){ seg[ind] = val; return; } ll mid = (l+r)/2; update(2*ind,l,mid,t,val); update(2*ind+1,mid+1,r,t,val); push(ind); } void solve() { cin >> n >> m; rep(i,0,1<<n) cin >> a[i]; build(1,0,(1<<n) - 1); rep(i,0,m){ ll j,val; cin >> j >> val; update(1,0,(1<<n)-1,--j,val); cout << seg[1] << endl; } }