1

Given an array of n elements. Initially all of them are zero. We need to process three type of queries:

  1. assign value v to all elements on the segment from l to r,
  2. add v to all elements on the segment from l to r,
  3. find the sum on the segment from l to r.

We can solve this problem by doing some simple loops. But the problem is there are as much as 100000 queries of these three types. So, this method will take much time. That's why I tried using segment tree and lazy propagation to solve this problem, but couldn't solve it. How to solve this problem?

This problem is from here.

Yeasin Mollik
  • 531
  • 6
  • 13
  • 3
    Change the name of the identifiers, they're not meaningful and makes the code harder to read. Also, provide a [minimal reproducible example](https://stackoverflow.com/help/minimal-reproducible-example). Also, [Why should I not #include ?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) – Rohan Bari Aug 18 '20 at 16:28
  • 1
    Everything about the shown codes shouts "competition site". You've fallen into the trap of using such sites for learning, and all you have really learnt are *bad habits*. Take classes and [read books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) to learn C++ and programming first. *Then* use competition sites to keep existing knowledge and *good* habits fresh. – Some programmer dude Aug 18 '20 at 16:33
  • @Someprogrammerdude Thanks. I need to improve my coding style. And I am updating this code to make it more readable. – Yeasin Mollik Aug 18 '20 at 16:37
  • When you say *"an array of n elements"* do you mean a `std::array` or a plain (C-style) array? If the former, then there are many STL routines that allow manipulation of element ranges; if the latter, then fairly simple loops will do the trick. What have you tried? – Adrian Mole Aug 18 '20 at 16:50
  • @AdrianMole This is a plain c-style array. And sorry I did not mention that there are `10^5` queries. I just edited my question to include this. – Yeasin Mollik Aug 18 '20 at 17:03
  • 2
    You can do all three operations in logarithmic time by maintaining two Fenwick trees, which is sufficient for the problem linked. See: https://www.geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/ – Ekesh Kumar Aug 18 '20 at 17:03
  • 1
    @EkeshKumar I get the range addition using bit. But, how range assign works using bit? Please elaborate – Yeasin Mollik Aug 18 '20 at 17:24
  • I see in your original code you were using an array-based segment tree. From personal experience, it is much easier to get used to the ins and outs of segment tree beauty by first using an object-based segment tree. That is, define a struct or a class for a segment tree node rather than having a global array. It's much more clear what's going on, imo. Good luck! – Jacob Steinebronn Aug 18 '20 at 18:44

0 Answers0