Graphs , Segment Tree - Class 2

Topics to be Covered :-

• Graphs
• Application of DFS
• Application of BFS
• Topological Sorting
• Strongly Connected Componenets( Do )
• Segment Tree
• Range Query, Point Update
• Point Query, Range Update( Do )
• Range Minimum Query(Next Class)
• Range Query, Range Update( Next Class )

----------------------------------------------------------------------------------------------------------------------------

BFS example : Spoj - ONE ZERO

• The problem can be solved using BFS. The number whose multiple we want to find is n. Since the number formed by 1 and 0 , X,  can be very large, we will maintain the modulus of X w.r.t. n.
• Assume a tree with "1" as the root. Every node has 2 child, left child is denoted by appending a "0" and right child is denoted by appending a "1".
                                           "1"
                                       /           \
                                   "10"          "11"
                                   /     \          /      \
                          "100"   "111"  "110"  "111"   .... and so on
• Suppose I am at some node, and the modular X value is val. So I will call my left child( 2*node) with value (val*10)%n and the right child(2*node+1) with value (val*10+1)%n.
• Proceeding this way, we will get more and more modular values. We want to reach a node where we finally get a 0 modular value. The actual X at this node will be divisible by n.(Why?)
  
• So why do we need to use BFS? We need BFS to get the minimum such element. As you can see the actual numbers(X) increase with the levels, and, in a particular level from left to right. So if we proceed in this order , we can get the minimum such element.
• Now we need to deal with the problem that some modular values will be repeated again and again and some modular values will never be reached. So it may be possible that we cannot reach modular value 0. How will we check for this?
      We will maintain a visited array. For a particular modular value, we will evaluate its sub-tree only for the first time. If we encounter the same modular value again, we will skip it and proceed with the next element in BFS algorithm.
• Now we will see how this is implemented. We will maintain a queue for BFS. We will start with number 1 in the queue.
      Now everytime we will get the front element( current_element ) of the queue. We will check all the neighbors of a particular node, and insert them at the end if they are not visited. Now we  will remove the front element and mark it as visited. We proceed in the following way until we reach a node when modular value is 0, or our queue becomes empty. If our queue becomes empty and we haven't reached an element whose modular value is 0, multiple of n of the required form does not exist! (Why?)
• To get the actual value of X, we can maintain an additional string S. Originally it is set as "1". We wemove left, "0" is appended. When we move right "1" is appended. When we reach a node where modular value becomes 0, S will contain the original X.

Try to code it now! Maybe we update the code later.

----------------------------------------------------------------------------------------------------------------------------

Topological Sorting

 

• It gives a logical ordering that you may follow to complete all the tasks by taking care of the dependencies among the tasks.
• It is applicable for directed acyclic graph.
      If the graph is cyclic, you cannot resolve the dependency. If the graph is undirected , there is no sense of ordering or dependency.
• It can be implemented via DFS.  

Try this question: Course Dilemma   

 Solution

-----------------------------------------------------------------------------------------------------------------------------

Segment Tree

It's one of the most important data structure from the perspective of competitive programming. It allows aggregation queries and updates over array intervals in logarithmic time.

• The simplest application of a Segment Tree is when you have Range Query and Point Update. Suppose you have the following problem : -

          " You are given an Array of Size N. Now there are many queries. Queries are of two types:-

• Query 1 : sum x y - gives the sum from index x to index y
• Query 2 : update x v - update value at index x to v"

           So how will you go about solving . Let's try some approaches without segment trees First.

1. The naive approach would be that loop for the
•  loop for the sum query - O(n)
•  change the value for update query - O(1)
  ( Good if the frequency of sum queries is very low )  
2. Another approach can be maintaining a cumulative sum array
• Get difference for sum query - O(1)
• Change the cumulative array - O(n)
  (Good if the frequency of update queries is very low)
  

  

But these approaches are not enough. For instance, there may be cases when both sum queries and update queries are almost equal. In such cases , all these approaches will time out. Luckily we can ask Segment Tree for help.

 We define the segment tree for the interval [i, j] in the following recursive manner:

• the first node will hold the sum for the interval [i, j]
• if i<j the left and right child will hold the sum for the intervals [i, (i+j)/2] and [(i+j)/2+1, j]
• the leaf nodes will contain the actual elements

Notice that the height of a segment tree for an interval with N elements is [logN] + 1. Here is how a segment tree for the interval [0, 9] would look like:

If we have a node numbered x that is not a leaf the left son of x is 2*x and the right son 2*x+1.


For solving the Range Sum problem using segment trees we should use an array SegTree[1, 2 * 2^{[logN] + 1}] where SegTree[i] holds the sum of interval assigned to node i. At the beginning all elements in SegTree should be -1. The tree should be initialized with the following function (b and e are the bounds of the current interval):

   

  vector<int> SegTree,A;

  int N; 

  #define left(i)  (2*i)

  #define right(i) (2*i+1) 

  ...

  void construct(int node, int b, int e)
  {
      if (b == e)
          SegTree[node] = A[b];
      else
       {
          //compute the values in the left and right subtrees
          construct(left(node), b, (b+e)/2);
          construct(right(node), (b+e)/2 + 1, e);
          SegTree[node]=SegTree[left(node)]+SegTree[right(node)]; 
      }
  }

The function above reflects the way the tree is constructed. When calculating the sum for some interval we should look at the values of its children. You should call the function with node = 1, b = 0 and e  = N-1.

We can now start making queries. If we want to find the sum of values in some interval [i, j] we should use the next easy function:

  int query(int node, int b, int e,int i, int j)
  {
      int p1, p2;
   
      //current_interval is completely outside required_interval 
      if (i > e || j < b)
          return 0;
   
     //current_interval is completely inside required_interval 
      if (b >= i && e <= j)
          return SegTree[node];
   
     //compute the minimum position in the 
     //left and right part of the interval
      p1 = query(left(node), b, (b+e)/2, i, j);
      p2 = query(right(node), (b+e)/2 + 1, e, i, j);
   
     //return the sum of the p1 & p2 
      return p1+p2;
  }

You should call this function with node = 1, b = 0 and e = N – 1, because the interval assigned to the first node is [0, N-1].
In case we want to update any particular index in the original array, we can make use of the following function:

  void update(int node, int b, int e,int index, int value)
  {
      if(b == e && b == index)

      {

          SegTree[node]=value;

          return;

      }

      int m=(b+e)/2;

      //current_interval is completely inside required_interval 

      if (index <= m)

         //go to the left child 

         update(left(node),b,m,index,value);
      else

        //go to the right child

         update(right(node),m+1,e,index,value);

      //update current 

      SegTree[node]=SegTree[left(node)]+SegTree[right(node)];

 }

It’s easy to see that any query is done in O(log N).

 Try the Range Minimum Query, based on similiar concept!
----------------------------------------------------------------------------------------------------------------------------