MrDepomposition's blog

hello
By MrDepomposition, history, 5 years ago, In English

hello i am writing this blog because i asked a question but havent got asnwer for it, please explain me why do we need to use segment tree to calculate sums, why cant we just use c++ operator + (read more about this operator here — https://www.w3schools.com/cpp/cpp_operators.asp)

  • Vote: I like it
  • -33
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope you're kidding

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The + operator in general won't give you the sum of an array over an index range [l...r] in log(N) time. A segment tree will.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    yes but + operator is O(1) while segment tree is logN, so we should use + operator, isnt it?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because you need to apply the + operator (r — l) = O(n) times to find the sum from l to r. With a segment tree, you can do this in O(log N)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        r — l = n it means that r — l — n = 0 so the complexity is O(0), right?

        → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

i am trying to solve this problem — https://mirror.codeforces.com/problemset/problem/409/H?locale=ru
but my segment tree solution fails

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Its big brain time!

→ Reply