Optimising Funny Marbles

Question

Problem statement is at http://www.codechef.com/DEC13/problems/MARBLEGF

Lira is given array A, which contains elements between 1000 and 2000. Three types of queries can be performed on this array: add a given value to a single element on it, subtract a given value from a single element on it and find the sum of the values between indexes i and j, i.e. A[i]+...+A[j]. Check input and example section for details.

Input

The first line of the input contains two integers: N and Q, denoting respectively, the number of students that there are present to receive the marbles as a gift and the number of actions Lira's mom will perform.

These actions can be of three different types:

• S i j - if the mom wants to find the sum of the number of marbles from students i to j.
• G i num_marbles - if the mom decides to give num_marbles to student i
• T i num_marbles - if the mom decides to take away num_marbles from student i

Output

The output should contain as many lines as the number of queries S and it should contain the answer for each query on a separate line

Constraints

• 2 ≤ N ≤ 1000000
• 3 ≤ Q ≤ 50000
• The array is 0-indexed.
• 1000 ≤ A[i] ≤ 2000
• A student can never have a negative value of marbles. (i.e. there's no data which can cause a student to have a negative value of marbles)
• 0 ≤ i, j ≤ N-1, and i ≤ j for the sum query
• At any given time, it is assured that the maximum number of marbles each student can have (num_marbles) never exceeds the size of the int data type.

Example

Input:

5 3
1000 1002 1003 1004 1005
S 0 2
G 0 3
S 0 2

Output:

3005
3008

My code gives time limit exceeded.

My code:

import java.util.*;

class funny_marbles
{
    public static void main(String[] ar)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        for(int i = 0; i < q; i++)
        {
            String s = sc.next();
            int t1 = sc.nextInt();
            int t2 = sc.nextInt();
            if(s.equals("S"))
            {
                long sum = 0;
                for(int j = t1; j <= t2; j++)
                    sum+=a[j];
                System.out.println(sum);
            }
            else if(s.equals("G"))
                a[t1]+=t2;
            else if(s.equals("T"))
                a[t1]-=t2;
        }
    }
}

Updated to use cumulative sum, but still exceeding time limit:

import java.util.*;

class funny_marbles
{
    public static void main(String[] ar)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++)
        {
            if(i == 0)
                a[i] = sc.nextInt();
             else
                a[i] = a[i-1] + sc.nextInt();
        }
        for(int i = 0; i < q; i++)
        {
            String s = sc.next();
            int t1 = sc.nextInt();
            int t2 = sc.nextInt();
            if(s.equals("S"))
            {
                int x;
                if(t1 == 0)
                    x = 0;
                else
                    x = a[t1-1];
                System.out.println(a[t2]-x);
            }
            else if(s.equals("G"))
            {
                update(a,t2);
            }
            else if(s.equals("T"))
            {
                update(a,-t2);
            }
        }
    }

    public static void update(int[] a, int t)
    {
        for(int i = 0; i < a.length; i++)
            a[i] += t;
    }
}

Answer 1

Given the constraints, the maximum sum, N * max(A), would be 2000000000, which fits within a Java int. You don't need a long.

Your code is a straightforward implementation of the challenge; there's nothing to micro-optimize. Your only hope is to use a different approach.

Assuming that the test is heavy on "S" queries, you would be better off keeping an array of cumulative sums. Then you could answer an "S" query in constant time.

What to do with "G" and "T" operations, though? The elegant approach would be to update the entire cumulative sums array for each "G" or "T". However, since N is likely to be larger than Q, you might get better performance keeping the "G" and "T" operations as a list of exceptions instead.