Trees

Some Facts about trees Simple path is a path that doesn’t contain any node twice. A tree has n-1 edges! Segment Trees Use segment trees for questions on updating values and querying. Can be used with complex operations like pairs,sets etc. Find very effecient and faster updating (used to insert too), by Finding path to root from one node. void update(int pos,int val){ pos += k; tree[pos] = val; int odd = 1; //this switches between alternate levels of the segment tree goes upwards while(pos>>=1 >0){ /* use this in case for level switching if(odd) tree[pos] = tree[2*pos] | tree[2*pos+1]; else tree[pos] = tree[2*pos] ^ tree[2*pos+1]; odd = 1-odd; */ tree[pos]=tree[2*pos]+tree[2*pos+1]; } } for(int i=0;i<n;i++){ int val; cin>>val; update(i,val); }