Linear Programming

Recently,i went through some stuff related to linear programming and found it worth sharing So i should start with the intro.
Comments

About Segment Trees

This is my first Blog on a Programming topic and well as you can see,i am starting with a challenging task to explain segment trees

So i will start with a problem that i came across in a recent competition and this would obviously lead you to the idea of using segment trees Here

Not sure if you actually read the problem or not but here it goes:

Motivation:In an array,if you are continuously asked to output f(array[i,j]) where f can be any function (eg:here,f is both maximum and minimum) then this stuff is very useful indeed

You may not like that but it is not the best technique for finding the value for any f.for example,if f is sum[i,j] then it has an O(1) technique for finding sum after a preprocess of O(N) .But still it is a lot better than using naive techniques such as finding f(array[i,j]) evertime you are asked.

Well the rest part is hopefully easy and just requires constructing the tree and using the query function.If you are lazy like me then you can just copy the code from here 

1
2
3

Time Complexities:
Construct:O(N)
Query:O(logn)

for constructing a tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 void initialize(intnode, int b, int e, int M[MAXIND], int A[MAXN], int N)
  {
      if (b == e)
          M[node] = b;
      else
       {
  //compute the values in the left and right subtrees
          initialize(2 * node, b, (b + e) / 2, M, A, N);
          initialize(2 * node + 1, (b + e) / 2 + 1, e, M, A, N);
  //search for the minimum value in the first and 
  //second half of the interval
          if (A[M[2 * node]] <= A[M[2 * node + 1]])
              M[node] = M[2 * node];
          else
              M[node] = M[2 * node + 1];
      }
  }

for query

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int j)
  {
      int p1, p2;


  //if the current interval doesn't intersect 
  //the query interval return -1
      if (i > e || j < b)
          return -1;

  //if the current interval is included in 
  //the query interval return M[node]
      if (b >= i && e <= j)
          return M[node];

  //compute the minimum position in the 
  //left and right part of the interval
      p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
      p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);

  //return the position where the overall 
  //minimum is
      if (p1 == -1)
          return p2;
      if (p2 == -1)
          return p1;
      if (A[p1] <= A[p2])
          return p1;
      return p2;

  }
Comments