Optimising Funny Marbles 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 &lt; n; i++)
            a[i] = sc.nextInt();
        for(int i = 0; i &lt; 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 &lt;= 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 &lt; n; i++)
        {
            if(i == 0)
                a[i] = sc.nextInt();
             else
                a[i] = a[i-1] + sc.nextInt();
        }
        for(int i = 0; i &lt; 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 &lt; a.length; i++)
            a[i] += t;
    }
}
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.