Fenwick Range Sum Class
PHP
Hard
6 views
Problem Description
You have an array of n integers. Support two operations: ADD i x (a[i]+=x) and SUM l r (inclusive). Print answers for SUM queries.
Input Format
Line1: n q. Line2: n integers. Next q lines commands.
Output Format
Outputs for SUM.
Sample Test Case
Input:
5 5
1 2 3 4 5
SUM 1 3
ADD 2 10
SUM 0 4
SUM 2 2
ADD 4 -5
Official Solution
<?php
class FenwickTree{
private $size;
private $tree=[];
function __construct($size){
$this->size=$size;
$this->tree=array_fill(0,$size+1,0);
}
function addAt($index,$delta){
$i=$index+1;
while($i<=$this->size){
$this->tree[$i]+=$delta;
$i += ($i & (-$i));
}
}
function prefixSum($index){
$i=$index+1;
$sum=0;
while($i>0){
$sum += $this->tree[$i];
$i -= ($i & (-$i));
}
return $sum;
}
function rangeSum($left,$right){
if($left>$right) return 0;
$rightSum=$this->prefixSum($right);
$leftSum=($left>0) ? $this->prefixSum($left-1) : 0;
return $rightSum-$leftSum;
}
}
$inputLines=preg_split('/\\R/', rtrim(stream_get_contents(STDIN)));
if(!$inputLines || trim($inputLines[0])==='') exit;
$firstParts=preg_split('/\\s+/', trim($inputLines[0]));
$n=intval($firstParts[0] ?? 0);
$q=intval($firstParts[1] ?? 0);
$initialTokens=preg_split('/\\s+/', trim($inputLines[1] ?? ''));
$fenwick=new FenwickTree($n);
for($pos=0;$pos<$n;$pos++) $fenwick->addAt($pos, intval($initialTokens[$pos] ?? 0));
$output=[];
for($lineNo=2;$lineNo<2+$q;$lineNo++){
$tokens=preg_split('/\\s+/', trim($inputLines[$lineNo] ?? ''));
$cmd=$tokens[0] ?? '';
if($cmd==='ADD'){
$fenwick->addAt(intval($tokens[1] ?? 0), intval($tokens[2] ?? 0));
}elseif($cmd==='SUM'){
$output[] = strval($fenwick->rangeSum(intval($tokens[1] ?? 0), intval($tokens[2] ?? 0)));
}
}
echo implode(PHP_EOL,$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!