arrays - Optimize queries performed on a subarray -

arrays - Optimize queries performed on a subarray -

i interviewed @ google. because of question process didn't move forwards after 2 rounds.

suppose given array of numbers. can given queries to:

find sum of values between indexes , j. update value @ index new given value. find maximum of values between indexes , j. check whether subarray between indexes , j, both inclusive, in ascending or descending order.

i gave him solution check subarray between indexes , j. asked me optimize it. thought of using hashtable if starting index same , ending index more previous found, store maximum , whether in ascending or descending , check remaining subarray. didn't optimize much required. i'd love know how can optimize solution create acceptable.

constraints:

everything [1,10^5]

thanks :)

all queries can answered in o(log n) time per query in worst case(with o(n) time preprocessing). can build segment tree , maintain sum, maximum , 2 boolean flags(they indicate whether range corresponds node sorted in ascending/descending order or not) each node. values can recomputed efficiently update query because o(log n) nodes can change(they lie on path root leaf corresponds changing element). other range queries(sum, max, sorted or not) decomposed o(log n) nodes(due properties of segment tree), , easy combine value of 2 nodes in o(1)(for example, sum result of combining 2 nodes sum of values these nodes).

here pseudo code. shows info should stored in node , how combine values of 2 nodes:

class node { bool is_ascending bool is_descending int sum int max int leftpos int rightpos } node merge(node left, node right) { res = node() res.leftpos = left.leftpos res.rightpos = right.rightpos res.sum = left.sum + right.sum res.max = max(left.max, right.max) res.is_ascending = left.is_ascending , right.is_ascending , array[left.rightpos] < array[right.leftpos] res.is_descending = left.is_descending , right.is_descending , array[left.rightpos] > array[right.leftpos] homecoming res }

arrays algorithm optimization dynamic-programming mathematical-optimization