Main Page

---

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);
    }