Range Sum Queries
PHP
Medium
4 views
Problem Description
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.
Sample Test Case
Input:
5 3
1 2 3 4 5
0 2
1 3
2 4
Official Solution
<?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);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!