Range Sum Queries

Range Sum Queries

Medium PHP PHP Arrays 24 views
Explanation Complexity

Problem Statement

Answer q range-sum queries on an array.

Input Format

Line1 n q. Line2 n ints. Next q lines l r (0-based).

Output Format

q lines sums.

Example

5 3
1 2 3 4 5
0 2
1 3
2 4
6
9
12

Constraints

n,q

Input / Output Format

Input Format
Line1 n q. Line2 n ints. Next q lines l r (0-based).
Output Format
q lines sums.
Constraints
n,q

Examples

Input:
5 3 1 2 3 4 5 0 2 1 3 2 4
Output:
6 9 12

Example Solution (Public)

PHP 
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$first=preg_split('/\\s+/', trim($inputLines[0] ?? ''));
$n=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$a=array_map('intval',preg_split('/\\s+/', trim($inputLines[1] ?? '')));
$pref=[0];
for($i=0;$i<$n;$i++) $pref[$i+1]=$pref[$i]+($a[$i] ?? 0);
$output=[];
for($i=0;$i<$q;$i++){
  $tokens=preg_split('/\\s+/', trim($inputLines[$i+2] ?? ''));
  $l=intval($tokens[0] ?? 0);
  $r=intval($tokens[1] ?? -1);
  $output[] = strval($pref[$r+1]-$pref[$l]);
}
echo implode(PHP_EOL,$output);
?>

Official Solution Code

<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$first=preg_split('/\\s+/', trim($inputLines[0] ?? ''));
$n=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$a=array_map('intval',preg_split('/\\s+/', trim($inputLines[1] ?? '')));
$pref=[0];
for($i=0;$i<$n;$i++) $pref[$i+1]=$pref[$i]+($a[$i] ?? 0);
$output=[];
for($i=0;$i<$q;$i++){
  $tokens=preg_split('/\\s+/', trim($inputLines[$i+2] ?? ''));
  $l=intval($tokens[0] ?? 0);
  $r=intval($tokens[1] ?? -1);
  $output[] = strval($pref[$r+1]-$pref[$l]);
}
echo implode(PHP_EOL,$output);
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.