How to improve the time complexity of this algorithm

Question

Here's a simple problem: I have this array of length N, and the function, which sets 2 borders (a, b), returns the sum of all elements in the array between a and b.

Now this is obviously O (N) time complexity ... but if I wanted to make it more efficient (e.g. log (N)), with a second data structure that stores partial sums, how can I execute it?

I was thinking about a binary tree, but cannot find an algorithm. Of course, I could just create an NxN matrix, but that's too much. I would like something that does not require too much space and allows me to logarithmically complicate the time; any idea?

UPDATE: I did not indicate it clearly .. but:

• boundaries are indicated in array indices, not values
• the array is dynamic, the values ​​can change, and I don't want to have linear complexity to change the value! Therefore, a simple partial sum algorithm does not work, I think ..
• no parallel programming (1 processor)

Answer 1

Well, you may have another array of the same size where you store partial amounts. Then, when you are given the boundaries, you can simply subtract the partial amounts and you will get the sum of the elements in this interval. For instance:

Elements: 1 2 3 4 5 6 Partial_Sum: 1 3 6 10 15 21 

Suppose, say, that the array starts with index = 0, and you want to get the sum of elements in the interval [1, 3] inclusive:

 // subtract 1 from the index of the second sum, because we // want the starting element of the interval to be included. Partial_Sum[3] - Partial_Sum[1-1] = 10 - 1 = 9 

Answer 2

It seems to me that the sums prefix can be used to respond to such requests in O(lg n) time.

EDIT: I was too fast - it can be done even faster. If you spend O(n) time (and O(n) extra memory) by preliminarily subtracting the sum array prefix (on a single-core computer), the answer to each request can be found O(1) times by subtracting the corresponding elements of this array. If you have n processors available, precompilation can be done in O(lg n) time.

Answer 3

I need to skip something in the question. Given an array of partial sums, you should be able to get constant complexity - the sum of elements from a to b is equal to partial_sums[b] - partial_sums[a] (or if you cannot accept a<b , partial_sums[max(a,b)] - partial_sums[min(a,b)] ).

Perhaps you are talking about a and b as value boundaries, not a location? If so, then assuming your array is sorted, you can get O (log N) complexity by using a binary search of the locations a and b , and then subtracting it as above. If the array is not sorted (and cannot be), you can do the same by creating an array of links to the source objects, sorting the links and creating partial sums for these links. This adds work to the preprocessing, but saves O (log N) for queries.

Edit: making a dynamic array should not have an effect, at least in terms of computational complexity. If you just insert / delete at the end of the main array, you can insert / delete in constant time in the partial sums array. To insert, you do something like:

 N = N + 1 main_array[N] = new_value partial_sum[N] = partial_sum[N-1] + new_value 

To remove from the end, you simply use N = N - 1 and ignore the values ​​earlier at the ends of both arrays.

If you need to support insert / delete in the middle of the main array, this takes linear time. An update of the partial sum array can also be performed in linear time. For example, to insert new_value into index i , you would do something like:

 N = N + 1 for location = N downto i + 1 main_array[location] = main_array[location-1] partial_sums[location] = partial_sums[location-1] + new_value 

Deletion is similar, except that you work your way from the delete point to the end and subtract the value to be deleted.

I really said “should” for some reason, although there is a possible reservation. If your array is extremely dynamic and the contents are floating point, you may / may encounter a problem: adding and subtracting values ​​repeatedly when inserting / deleting elements can (and ultimately) lead to rounding errors. In these conditions, you have several options: you need to abandon the idea altogether. In another case, even more storage is used - when adding / removing items, keep the current sum of the absolute values ​​of the items that were added / subtracted. If / if it exceeds the selected percentage of the partial amount for this point, you recalculate your partial amounts (and zero current amount).

Answer 4

Well, maybe I found a solution to have log (n) for both the change value and the sum and with linear overhead.

I will try to explain: we are building a binary tree, where the leaves are the values ​​of the array, in the order in which they are in the array (not sorted, not sorted tree).

Then we create the bottom from the bottom up, merging 2 sheets at a time, and put their amount in the parent. For example, if the array has a length of 4 and values ​​[1,5,3,2], we will have a tree with 3 levels, the root will be the total amount (11), and the rest will be 1 + 5-> 6 and 3 + 2-> 5

Now, to change the value, we need to update this tree (log n), and to calculate the sum, I developed this algorithm (log n):

acc = 0 // Battery

starting at the bottom, we climb a tree. I go up to the left (the current node is the correct descendant), then acc + = current_node - parent_node. If we go up (the current node is the left child), we do nothing.

then we do the same from the upper bound, of course, in this case it is the opposite (we make the sum if we go up)

we do this alternating, once at the lower boundary, once at the upper boundary. If we get that we get 2 node, we are actually the same node, then we sum the value of this node with the battery and return the battery.

I know that I didn’t explain it very well. It's hard for me to explain. Anyone got it?

Answer 5

There are two cases: static data or dynamic (changing) data

1. Static data

For static data, this is a well-known issue. First, calculate the “sum table” (an array of n + 1 elements):

 st[0] = 0; for (int i=0,n=x.size(); x<n; x++) st[i] = st[i-1] + x[i]; 

then to calculate the sum of the elements between a and b you just need to do

 sum = st[b] - st[a]; 

The algorithm can also be used in higher dimensions. For example, if you need to calculate the sum of all values ​​between (x0, y0) and (x1, y1), you can simply do

 sum = st[y0][x0] + st[y1][x1] - st[y0][x1] - st[y1][x0]; 

where st[y][x] is the sum of all the elements above and to the left of (x, y) .

Calculating the sum table is an O (n) operation (where n is the number of elements, for example rows*columns for a 2d matrix), but for very large data sets (for example, images), you can write the optimal parallel version that can work in O ( n / m) , where m is the number of available CPUs. This is what I found quite unexpected ...

Performing a simple (single-threaded) calculation of the sum table in the case of 2d:

 for (int y=0; y<h; y++) for (int x=0; x<w; x++) st[y+1][x+1] = st[y+1][x] + st[y][x+1] - st[y][x] + value[y][x]; 

2.Dynamic data

Instead of dynamic data, you can use what can be called "multi-mode":

 void addDelta(std::vector< std::vector< int > >& data, int index, int delta) { for (int level=0,n=data.size(); level<n; level++) { data[level][index] += delta; index >>= 1; } } int sumToIndex(std::vector< std::vector< int > >& data, int index) { int result = 0; for (int level=0,n=data.size(); level<n; level++) { if (index & 1) result += data[level][index-1]; index >>= 1; } return result; } int sumRange(std::vector< std::vector< int > >& data, int a, int b) { return sumToIndex(data, b) - sumToIndex(data, a); } 

Basically, at each "level" a cell contains the sum of two cells of the next more subtle levels. When you add data to the lowest (higher) level, you should also add it to higher levels (this is what addDelta does). To calculate the sum of all values ​​from 0 to x , you can use higher levels to accumulate calculations ... see the following figure:

Finally, to get the sum from a to b , you simply calculate the difference between the two sums, starting at 0.

Answer 6

In accordance with the instruction of the problem, you are given an array of numbers and a pair of indices representing the boundaries of the interval, the contents of which should be summed. Since there is no search in this problem, presenting data in the form of a binary tree structure does not give advantages in terms of the complexity of time or space.

Since you cannot execute your decision in a multiprocessor environment, you are stuck with O (N).

If your solution was allowed to run in a multiprocessor environment, the optimal complexity would be O (N / p + p + 1), where p is the number of available processors. This is because in this case you could divide the interval into p-intervals (+1), sum the intervals in parallel (N / p) and then sum the result of each individual sub-interval (+ p) to complete the calculation.

Answer 7

Create a balanced binary tree that sorts numbers according to their value. This can be done so that each operation performs linear time. In each node, keep the sum of all the values ​​below the node. To calculate the sum of the values ​​in the range [a, b], you must go down this tree for both a and b and add the corresponding values. O (ln n) every time you calculate a sum or change a value.