JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
A problem on Data Structure | Reply
I have an Array ar[50000]
Values are stored here can be atmost 1000
Now,I need to do queries
[i<=j]
max(i,j)->maximum value of the range (ar[i],ar[i+1],,,ar[j])
update(i,j,a)->update the value (ar[i],ar[i+1],,,ar[j])by a (a can be positive or negative number)
initially Array ar has all elements zero
And (j-i) will be atmost 10^4 in max(i,j) and update(i,j,a) functions.
How fast can I do such operations and using which data structures?
[for max and update functions ; probably I don't want to go for 5*10^4 iterations for each]
Re: A problem on Data Structure (response to post by rockaustin2k6) | Reply
> update(i,j,a)->update the value (ar[i],ar[i+1],,,ar[j])by a (a can be positive or negative number)

"update by a" means adding a to all elements in the interval?

It can be solved using segment tree. Each node of the tree corresponds to some segment i..j. If i == j then it's a leaf node, otherwise it has two child nodes that correspond to i..(i+j)/2 and (i+j)/2+1..j. Node stores two numbers:

add - a number that should be added to all elements on this interval (for example, to get an actual value of ar[i] we need to sum all 'add' values on the path from the root to the leaf i..i).

max - the maximum number we can get if we go from this node to some leaf summing 'add' values on the way.

Here's pseudocode of max and update:

function get_max(cur_node, i, j) {
  i = max(i, cur_node.i)
  j = min(j, cur_node.j)
  if (i > j) return -infinity
  if (i == cur_node.i and j == cur_node.j) return cur_node.max
  res = max(get_max(cur_node.left_child, i, j), get_max(cur_node.right_child, i, j))
  res += cur_node.add
  return res
}
 
function update(cur_node, i, j, a) {
  i = max(i, cur_node.i)
  j = min(j, cur_node.j)
  if (i > j) return
  if (i == cur_node.i and j == cur_node.j) {
    cur_node.add += a
    cur_node.max += a
    return
  }
  update(cur_node.left_child, i, j, a)
  update(cur_node.right_child, i, j, a)
  cur_node.max = max(cur_node.left_child.max, cur_node.right_child.max) + cur_node.add
}


Of course, it's just pseudocode and we don't actually need objects representing nodes and the tree can be stored in just two arrays add and max.
RSS