title: Conditional Multiplication and Cumulative sum
body: <p>Recently I came across a coding question and I wanted to find the algorithm for it. </p>
  
  <pre><code>Array is 1-based array.
  Query types: 
  1 L R X K : Multiply from L to R with K if it is less than X
  2 L R: Print the sum from L to R
  
  INPUT:
  6 5
  5 4 3 2 6 1
  Q1: 1 2 3 5 4
  Q2: 2 1 2
  Q3: 1 1 3 4 5 
  Q4: 2 3 4
  Q5: 2 4 5
  
  OUTPUT:
  21
  14
  8
  
  Explantion:
  Q1: 5 16 12 2 6 1
  Q2: Print 21(5+16)
  Q3: 5 16 12 2 6 1
  Q4: Print 14 (12+2)
  Q5: Print 8 (2+6)
  </code></pre>
  
  <p>Generally here each query takes O(n) complexity to solve. But the algorithm should solve it in even less time.How can I do that?</p>