Блог пользователя MrDepomposition

hello
Автор MrDepomposition, история, 5 лет назад, По-английски

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)

  • Проголосовать: нравится
  • -33
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope you're kidding

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Its big brain time!

→ Ответить