# Storing and processing large arrays to compute dot products

Problem Statement (from HackerRank)

We have two arrays $a$ and $b$ of length $N$, initially all values equals to zero. We have $Q$ operations. Let's define three types of operations on this arrays:

• 1 l r c: Increase $a_l, a_{l+1}, \ldots, a_r$ by $c$.
• 2 l r c: Increase $b_l, b_{l+1}, \ldots, b_r$ by $c$.
• 3 l r: Print $a_l\cdot b_l + a_{l+1}\cdot b_{l+1} +\ldots+ a_r\cdot b_r$ in modulo $1000000007$.

Input Format

First line of the input consists of $N$ and $Q$. Next $Q$ lines contain one of the three types of operations.

Constraints

• $1 \le N \le 10^9$
• $1 \le Q \le 200000$
• $1 \le c \le 10000$
• $1 \le l \le r \le N$

Output Format

Whenever you get a type 3 operation, you should print the answer in a new line.

Sample Input 1

5 3
1 1 5 5
2 2 4 2
3 3 4


Sample Output 1

20


Sample Input 2

10 20
1 9 9 6768
2 5 5 2202
3 7 7
2 3 9 1167
2 1 7 8465
3 1 5
2 1 1 1860
3 9 9
2 5 5 2153
1 5 7 749
3 1 1
2 8 10 3129
3 1 1
1 2 10 2712
2 1 8 79
1 1 6 4645
1 7 7 1358
3 2 10
1 9 9 8677
3 8 10


Sample Output 2

0
0
7898256
0
0
506356461
98353320


How can I efficiently store and process data for this problem?

#include<stdio.h>
#include<string.h>
int main()
{
long n,q,ch,l,r,c,i,j;
/* n, q, l, r, c works as per problem statement.
ch is used to scan the first digit of operation.
i and j are used to control the loops. */
scanf("%ld %ld",&n,&q);
long a[n],b[n];
memset(&a, 0, sizeof a);
memset(&b, 0, sizeof b);
for(i=0;i<n;i++)    //Init to 0
{
a[i]=0;
b[i]=0;
}
for(i=0;i<q;i++)
{
scanf("%ld ",&ch);  //Look for the first digit
switch(ch)
{
case 1:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(j=l;j<r;j++)
a[j]+=c;    //Adds c to every element of a
break;
case 2:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(j=l;j<r;j++)
b[j]+=c;    //Adds c to every element of b
break;
case 3:
scanf("%ld %ld",&l,&r);
l--;
c=0;
for(j=l;j<r;j++)
printf("%ld\n",c%1000000007);   //Prints the value after using mod
break;
}
}
}

• Another thing you might try is to use multi-threading, and to use SIMD. You don't say what platform you're on, but you could look into pthreads, GCD, threaded building blocks, OpenMP for multi-threading. For SIMD, you can look into SSE, AVX, Neon, AltiVec, etc. – user1118321 Sep 13 '15 at 14:28
• Please declare cross-postings in the future. – 200_success Sep 13 '15 at 17:45

This is a fairly straightforward implementation that seems to get the job done at least for the simple input you posted. Overall, it's easy to read and understand, given the problem description. Here are some ways I think it could be improved.

# Naming

You've named all the variables similarly to how they are named in the problem statement. That's fine for an assignment or exercise, but it would be a real pain to maintain later on. You have a comment describing the names, but it assumes the person reading it has the problem statement. That's rarely the case in the real world.

The variable names n, i, and j aren't terrible. I'd leave i and j, but rename n to something descriptive like numElements (or, if you prefer num_elements).

The names q, l, ch, r, and c are terrible and confusing. I'd make q something like numLines or numInputLines or something like that. l and r are the start and end of the range of indexes you want to modify, so I'd name them start and end.

c and ch are likely to be confused. Also, ch seems like it's a remnant from an earlier version when it was declared as a char type instead of a long. It's used to get the user's input, so you could name it userInput or mode or something more appropriate. c is the value you're adding to all the inputs. Since this is an exercise, it's just an abstract value that doesn't have any real meaning. Normally, I'd suggest calling it whatever it is, but that's hard in this case. Something generic like value or operand could work.

# Functions

Your code does a few different things:

1. Gets the size of the arrays and number of lines of input
2. Creates and initializes the arrays
3. Processes the inputs

You should separate those into functions like this:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int getNumberOfElementsAndLines (size_t* outElements, size_t* outLines)
{
long numScanned = scanf("%zu %zu", outElements, outLines);
int result = (numScanned == 2);
if ((*outElements < 1) || (*outElements > 1000000000) || (*outLines < 1) || (*outLines > 200000))
{
result = 0;
}

return result;
}

int allocateAndInitArrays (const size_t numElements, long** outA, long** outB)
{
// Make sure the inputs are valid
if ((outA == NULL) || (outB == NULL) || (numElements == 0))
{
return 0;
}

// Allocate and clear A and if successful, allocate and clear B
*outA = calloc (numElements, sizeof(**outA));
*outB = calloc(numElements, sizeof(**outB));

if (*outB == NULL)
{
free(*outA);
*outA = NULL;
}

return ((*outA != NULL) && (*outB != NULL));
}

int getAndProcessInput (long* a, long* b, const size_t numElements, const size_t numLines)
{
for (size_t i = 0; i < numLines; i++)
{
long mode   = 0;
int numScanned = scanf("%ld ", &mode);
if (numScanned != 1)
{
return 0;
}

long l, r, c;
switch (mode)
{
case 1:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(long j = l; j < r; j++)
a[ j ] += c;    //Adds c to every element of a
break;

case 2:
scanf("%ld %ld %ld",&l,&r,&c);
l--;
for(long j = l; j < r; j++)
b[ j ] += c;    //Adds c to every element of b
break;

case 3:
scanf("%ld %ld",&l,&r);
l--;
c=0;
for(long j = l; j < r; j++)
c += a[ j ] * b[ j ];   //Adds the product
printf("%ld\n",c%1000000007);   //Prints the value after using mod
break;

default:
// Error in input
return 0;
break;
}
}

return 1;
}


Then your main would look something like this:

int main()
{
int     result  = 0;
size_t  numElements = 0;
size_t  numLines = 0;
result = getNumberOfElementsAndLines(&numElements, &numLines);

long*   a = NULL;
long*   b = NULL;
if (result == 1)
{
result = allocateAndInitArrays(numElements, &a, &b);
}

if (result == 1)
{
result = getAndProcessInput(a, b, numElements, numLines);
}

free(a);
free(b);

return result;
}


# Memory

You'll notice above that I used calloc() to allocate the memory on the heap instead of the stack. Stack space is limited, and there's a lot more memory available on the heap. That may fix your issue getting a segfault.

# Error Handling

I added a little bit of error handling. It needs more. You should check to make sure you got valid results from functions like scanf(), for example. What if the user entered a negative number? What if they entered 0? Etc.

• 1. Why the temporary in GetNumberOfElementsAndLines? Actually, even putting that into a function by itself is severe overkill unless it's called often. 2. The guard-clause in allocateAndInitArrays, even if there was any reason not to make it a simple assert, is far too verbose and contains a tautology: !pointer is a far better way to check for nullpointers, and any unsigned value is always >=0. 3. Use sizeof with the expression of the correct type instead of determining that manually for added resiliency. – Deduplicator Sep 12 '15 at 23:29
• 4. There's no excuse to using convoluted logic and data-flow to force a single exit. 5. In getAndProcessInput you fail to check the result of scanf. 6. Securing free against passing a null-argument is simply silly. 7. Sweeping the carpets before ordering the wrecking-crew is pointless at best, and a useless annoyance to the user at worst. – Deduplicator Sep 12 '15 at 23:33
• @Deduplicator 1) Several reasons: This code looks like an exercise for a beginner. It's clearer to show that scanf() has a return value. (Most pros I know forget that!) Also, as alluded to later, there should also be a check to ensure the inputs were valid values. 2) If this were production code, I'd probably make it an assert. Again, since this seemed like a beginner, I spelled it out. I originally had longs instead of size_ts, and must have missed that. Thanks for pointing it out. 3) Excellent point! 4) I'm not sure what you're referring to. – user1118321 Sep 13 '15 at 1:18
• 5) Yep. I got a little sloppy. Thanks for catching that. 6) Ah shoot! I knew I could simplify that. Thanks. 7) I don't have any idea what that means or what it's referring to. – user1118321 Sep 13 '15 at 1:18
• @user1118321: In each of the cases, how do I process the inputs? With my code or by some other process? – Somnath Rakshit Sep 13 '15 at 1:25

# Fenwick tree

Instead of using a normal array, you could use a Fenwick tree to store each of the two arrays. Fenwick trees can do range updates (operations 1 and 2) in logarithmic time instead of linear time. The third operation would require $O(n\log n)$ time instead of $O(n)$ time, so I suppose if there were a lot of those operations, it could make things slower.

# Sample implementation

I wrote this sample implementation to show how a Fenwick tree could solve this problem. I combined the Fenwick tree with an additional update array to do the dot product step in linear time. The update array simply stores the change in value from one array index to the next.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

void rangeUpdate(long *tree, long treeSize,
long left, long right, long value)
{
while (left < treeSize) {
tree[left] += value;
left |= (left + 1);
}
right++;
while (right < treeSize) {
tree[right] -= value;
right |= (right + 1);
}
}

long getVal(const long *tree, long treeSize, long i)
{
long ret = 0;

while (i >= 0) {
ret += tree[i];
i &= i + 1;
i--;
}
return ret;
}

int main(void)
{
long  arraySize  = 0;
long  numQueries = 0;
long *tree1      = NULL;
long *tree2      = NULL;
long *update1    = NULL;
long *update2    = NULL;

if (scanf("%ld %ld\n", &arraySize, &numQueries) != 2)
exit(1);
arraySize += 2;
tree1   = calloc(arraySize, sizeof(*tree1));
tree2   = calloc(arraySize, sizeof(*tree2));
update1 = calloc(arraySize, sizeof(*tree1));
update2 = calloc(arraySize, sizeof(*tree2));
if (tree1 == NULL || tree2 == NULL || update1 == NULL || update2 == NULL)
exit(1);
for (long i = 0; i < numQueries; i++) {
long operation = 0;
long left      = 0;
long right     = 0;
long value     = 0;
if (scanf("%ld", &operation) != 1)
exit(1);
switch (operation) {
case 1:
case 2:
{
long *tree   = (operation == 1) ? tree1 : tree2;
long *update = (operation == 1) ? update1 : update2;
if (scanf("%ld %ld %ld\n", &left, &right, &value) != 3)
exit(1);
rangeUpdate(tree, arraySize, left, right, value);
update[left]    += value;
update[right+1] -= value;
break;
}
case 3:
{
long     val1   = 0;
long     val2   = 0;
uint64_t result = 0;

if (scanf("%ld %ld\n", &left, &right) != 2)
exit(1);

val1   = getVal(tree1, arraySize, left);
val2   = getVal(tree2, arraySize, left);
result = (uint64_t) val1 * val2;
for (long i = left+1; i <= right; i++) {
val1 += update1[i];
val2 += update2[i];
result += (uint64_t) val1 * val2;
}
printf("%ld\n", (long) (result % 1000000007));
break;
}
}
}
}

• Will it be possible for you to show some code implementation? – Somnath Rakshit Sep 13 '15 at 1:30
• @SomnathRakshit On Code Review, we sometimes just push you in the right direction. It is still up to you to do the real work. – Simon Forsberg Sep 13 '15 at 14:01

For N = 109 you have to store about 7.4 GB data, if you merely use longs with a size of 4 bytes.

This is not feasible, which, I assume, is the whole point of the problem.

You have 200000 Qs - storing the Qs instead takes up only 11 bytes per Q - one byte to determine the operation, 8 bytes for the two values which can go up to 109and 2 bytes for c, which fits into 16 bits, as it's not higher than 10000.

If you store Q, you end up with around 2 MB of data.

You could apply the Q operations at runtime to a single long (long) and then print each value individually. This algorithm will be memory-efficient, but very very slow.

Looking at the problem, we will have a lot of array members having the same value. There are only 200000 operations but 1000000000 array entries - we can change 200000 different values - if we do this, we still have (109 - 200000) array entries with the very same value. Even if we modify 200000 ranges, this doesn't change the fact, merely the distribution of distinct values. So it's much more efficient to store a value and then for which array range this value is valid.

In example:

value 0 - [0,4343] [489289,999999999]
value 3 - [4344,4345]
value 7 - [4346,489288]


This is a mixture of storing the value and storing the operation. When you need to print a value, you look up the range and print the value.

As you see, we need less than 64 bytes for this simple example to store the information how the 7.4 GB data is compromised of, yet we can print the value for each and every array position.

Even if we have reduced the data, we still need to optimize the remaining data. We can't just dump it into a linked list - as stated, we can end up with Q+1 entries (200001), we can't afford to search the entries with an effort of O(n), let alone (r-l) * O(n).

But if we put the data into a binary search tree, we can find the correct array entry in 18 steps within the 200000 entries. This costs us some more memory, not only due to the overhead, but as we need the array index as key, we can't group all identical values together, just as long as they are one range. So the example above will need 4 nodes in the binary search tree, to separate the value 0 twice.

So, when you combine these two approaches, you should be able to get a decent memory and processor time consumption.