You are not logged in. Please login at www.codechef.com to post your questions!

×

How to do range update and range query simultaneously?

I need a way to find solve this :

Given array, use one of two operations. add k to all elements in a given interval, find sum of values in a given interval (both range update and range query simultaneously). I know how to do it using Fenwick tree data structure. I need it using segment tree. Can any one please provide a link to a tutorial?

in reference to the problem : http://www.spoj.com/problems/HORRIBLE/

Can it be done without lazy propagation?

p.s. I found this simple solution http://codeforces.com/blog/entry/6415. Can anyone explain it a bit please? I am confused with two variables in the segment tree. Please help

asked 14 Aug '15, 12:07

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

edited 14 Aug '15, 16:10


https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

use the above link for the basic idea about the segment trees useful for range queries and the next link for lazy propagation in the segment trees which is useful for the range updates.

http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html

link

answered 14 Aug '15, 12:44

vjvishjn's gravatar image

3★vjvishjn
312
accept rate: 0%

Hey, can this be done without lazy propagation? I am not worried about strict time limit.

(14 Aug '15, 13:07) dragonemperor3★

Hi dragonemperor,

if you are not worried about time limit then :

all type of problem which are solved by lazy propagation can be definitely solve by segment tree because lazy propagation concept is introduced due to high time complexity of segment tree so your update will take O(n) and query take O(long(n)) because updating tree is like updating array you have to update all children + parent node within that range means you have to update each single element within range as you do update in binary search tree and store sum in parent node i.e it will not make any sense :(

link

answered 14 Aug '15, 23:10

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14

question asked: 14 Aug '15, 12:07

question was seen: 2,650 times

last updated: 14 Aug '15, 23:10