JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm A problem on Data Structure
 A problem on Data Structure | Reply I have an Array ar[50000]Values are stored here can be atmost 1000Now,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 zeroAnd (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.
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm A problem on Data Structure Previous Thread  |  Next Thread