// C++ program to demonstrate Range Update // and Point Queries Without using BIT #include    using namespace std; // Updates such that getElement() gets an increased // value when queried from l to r. void update(int arr[] int l int r int val) {  arr[l] += val;  arr[r+1] -= val; } // Get the element indexed at i int getElement(int arr[] int i) {  // To get ith element sum of all the elements  // from 0 to i need to be computed  int res = 0;  for (int j = 0 ; j <= i; j++)  res += arr[j];  return res; } // Driver program to test above function int main() {  int arr[] = {0 0 0 0 0};  int n = sizeof(arr) / sizeof(arr[0]);  int l = 2 r = 4 val = 2;  update(arr l r val);  //Find the element at Index 4  int index = 4;  cout << 'Element at index ' << index << ' is ' <<  getElement(arr index) << endl;  l = 0 r = 3 val = 4;  update(arrlrval);  //Find the element at Index 3  index = 3;  cout << 'Element at index ' << index << ' is ' <<  getElement(arr index) << endl;  return 0; } 

// Java program to demonstrate Range Update  // and Point Queries Without using BIT  class GfG {  // Updates such that getElement() gets an increased  // value when queried from l to r.  static void update(int arr[] int l int r int val)  {   arr[l] += val;  if(r + 1 < arr.length)  arr[r+1] -= val;  }  // Get the element indexed at i  static int getElement(int arr[] int i)  {   // To get ith element sum of all the elements   // from 0 to i need to be computed   int res = 0;   for (int j = 0 ; j <= i; j++)   res += arr[j];   return res;  }  // Driver program to test above function  public static void main(String[] args)  {   int arr[] = {0 0 0 0 0};   int n = arr.length;   int l = 2 r = 4 val = 2;   update(arr l r val);   //Find the element at Index 4   int index = 4;   System.out.println('Element at index ' + index + ' is ' +getElement(arr index));   l = 0;  r = 3;  val = 4;   update(arrlrval);   //Find the element at Index 3   index = 3;   System.out.println('Element at index ' + index + ' is ' +getElement(arr index));  } }  

# Python3 program to demonstrate Range  # Update and PoQueries Without using BIT  # Updates such that getElement() gets an  # increased value when queried from l to r.  def update(arr l r val): arr[l] += val if r + 1 < len(arr): arr[r + 1] -= val # Get the element indexed at i  def getElement(arr i): # To get ith element sum of all the elements  # from 0 to i need to be computed  res = 0 for j in range(i + 1): res += arr[j] return res # Driver Code if __name__ == '__main__': arr = [0 0 0 0 0] n = len(arr) l = 2 r = 4 val = 2 update(arr l r val) # Find the element at Index 4  index = 4 print('Element at index' index 'is' getElement(arr index)) l = 0 r = 3 val = 4 update(arr l r val) # Find the element at Index 3  index = 3 print('Element at index' index 'is' getElement(arr index)) # This code is contributed by PranchalK 

// C# program to demonstrate Range Update  // and Point Queries Without using BIT  using System; class GfG  {  // Updates such that getElement()  // gets an increased value when // queried from l to r.  static void update(int []arr int l   int r int val)  {   arr[l] += val;   if(r + 1 < arr.Length)   arr[r + 1] -= val;  }  // Get the element indexed at i  static int getElement(int []arr int i)  {   // To get ith element sum of all the elements   // from 0 to i need to be computed   int res = 0;   for (int j = 0 ; j <= i; j++)   res += arr[j];   return res;  }  // Driver code  public static void Main(String[] args)  {   int []arr = {0 0 0 0 0};   int n = arr.Length;   int l = 2 r = 4 val = 2;   update(arr l r val);   //Find the element at Index 4   int index = 4;   Console.WriteLine('Element at index ' +   index + ' is ' +  getElement(arr index));   l = 0;   r = 3;   val = 4;   update(arrlrval);   //Find the element at Index 3   index = 3;   Console.WriteLine('Element at index ' +   index + ' is ' +  getElement(arr index));  }  }  // This code is contributed by PrinciRaj1992 

 // PHP program to demonstrate Range Update  // and Point Queries Without using BIT  // Updates such that getElement() gets an  // increased value when queried from l to r.  function update(&$arr $l $r $val) { $arr[$l] += $val; if($r + 1 < sizeof($arr)) $arr[$r + 1] -= $val; } // Get the element indexed at i  function getElement(&$arr $i) { // To get ith element sum of all the elements  // from 0 to i need to be computed  $res = 0; for ($j = 0 ; $j <= $i; $j++) $res += $arr[$j]; return $res; } // Driver Code $arr = array(0 0 0 0 0); $n = sizeof($arr); $l = 2; $r = 4; $val = 2; update($arr $l $r $val); // Find the element at Index 4  $index = 4; echo('Element at index ' . $index . ' is ' . getElement($arr $index) . 'n'); $l = 0; $r = 3; $val = 4; update($arr $l $r $val); // Find the element at Index 3  $index = 3; echo('Element at index ' . $index . ' is ' . getElement($arr $index)); // This code is contributed by Code_Mech ?> 

//JavaScript program to demonstrate Range Update // and Point Queries Without using BIT // Updates such that getElement() gets an increased // value when queried from l to r. function update(arr l r val) {  arr[l] += val;  arr[r+1] -= val; } // Get the element indexed at i function getElement(rr i) {  // To get ith element sum of all the elements  // from 0 to i need to be computed  let res = 0;  for (let j = 0 ; j <= i; j++)  res += arr[j];  return res; } // Driver program to test above function  let arr = [0 0 0 0 0];  let n = arr.length;  let l = 2 r = 4 val = 2;  update(arr l r val);  // Find the element at Index 4  let index = 4;  console.log('Element at index 'index' is 'getElement(arr index));  l = 0 r = 3 val = 4;  update(arrlrval);  // Find the element at Index 3  index = 3;  console.log('Element at index 'index' is 'getElement(arr index)); // This code is contributed by vikkycirus 

// C++ code to demonstrate Range Update and // Point Queries on a Binary Index Tree #include    using namespace std; // Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. void updateBIT(int BITree[] int n int index int val) {  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;  // Traverse all ancestors and add 'val'  while (index <= n)  {  // Add 'val' to current node of BI Tree  BITree[index] += val;  // Update index to that of parent in update View  index += index & (-index);  } } // Constructs and returns a Binary Indexed Tree for given // array of size n. int *constructBITree(int arr[] int n) {  // Create and initialize BITree[] as 0  int *BITree = new int[n+1];  for (int i=1; i<=n; i++)  BITree[i] = 0;  // Store the actual values in BITree[] using update()  for (int i=0; i<n; i++)  updateBIT(BITree n i arr[i]);  // Uncomment below lines to see contents of BITree[]  //for (int i=1; i<=n; i++)  // cout << BITree[i] << ' ';  return BITree; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] int getSum(int BITree[] int index) {  int sum = 0; // Initialize result  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;  // Traverse ancestors of BITree[index]  while (index>0)  {  // Add current element of BITree to sum  sum += BITree[index];  // Move index to parent node in getSum View  index -= index & (-index);  }  return sum; } // Updates such that getElement() gets an increased // value when queried from l to r. void update(int BITree[] int l int r int n int val) {  // Increase value at 'l' by 'val'  updateBIT(BITree n l val);  // Decrease value at 'r+1' by 'val'  updateBIT(BITree n r+1 -val); } // Driver program to test above function int main() {  int arr[] = {0 0 0 0 0};  int n = sizeof(arr)/sizeof(arr[0]);  int *BITree = constructBITree(arr n);  // Add 2 to all the element from [24]  int l = 2 r = 4 val = 2;  update(BITree l r n val);  // Find the element at Index 4  int index = 4;  cout << 'Element at index ' << index << ' is ' <<  getSum(BITreeindex) << 'n';  // Add 2 to all the element from [03]  l = 0 r = 3 val = 4;  update(BITree l r n val);  // Find the element at Index 3  index = 3;  cout << 'Element at index ' << index << ' is ' <<  getSum(BITreeindex) << 'n' ;  return 0; } 

/* Java code to demonstrate Range Update and * Point Queries on a Binary Index Tree. * This method only works when all array * values are initially 0.*/ class GFG {  // Max tree size  final static int MAX = 1000;  static int BITree[] = new int[MAX];  // Updates a node in Binary Index  // Tree (BITree) at given index  // in BITree. The given value 'val'  // is added to BITree[i] and  // all of its ancestors in tree.  public static void updateBIT(int n   int index   int val)  {  // index in BITree[] is 1   // more than the index in arr[]  index = index + 1;  // Traverse all ancestors   // and add 'val'  while (index <= n)  {  // Add 'val' to current   // node of BITree  BITree[index] += val;  // Update index to that   // of parent in update View  index += index & (-index);  }  }  // Constructs Binary Indexed Tree   // for given array of size n.  public static void constructBITree(int arr[]  int n)  {  // Initialize BITree[] as 0  for(int i = 1; i <= n; i++)  BITree[i] = 0;  // Store the actual values   // in BITree[] using update()  for(int i = 0; i < n; i++)  updateBIT(n i arr[i]);  // Uncomment below lines to   // see contents of BITree[]  // for (int i=1; i<=n; i++)  // cout << BITree[i] << ' ';  }  // SERVES THE PURPOSE OF getElement()  // Returns sum of arr[0..index]. This   // function assumes that the array is  // preprocessed and partial sums of  // array elements are stored in BITree[]  public static int getSum(int index)  {  int sum = 0; //Initialize result  // index in BITree[] is 1 more   // than the index in arr[]  index = index + 1;  // Traverse ancestors  // of BITree[index]  while (index > 0)  {  // Add current element   // of BITree to sum  sum += BITree[index];  // Move index to parent   // node in getSum View  index -= index & (-index);  }  // Return the sum  return sum;  }  // Updates such that getElement()   // gets an increased value when   // queried from l to r.  public static void update(int l int r   int n int val)  {  // Increase value at   // 'l' by 'val'  updateBIT(n l val);  // Decrease value at  // 'r+1' by 'val'  updateBIT(n r + 1 -val);  }  // Driver Code  public static void main(String args[])  {  int arr[] = {0 0 0 0 0};  int n = arr.length;  constructBITree(arrn);  // Add 2 to all the  // element from [24]  int l = 2 r = 4 val = 2;  update(l r n val);  int index = 4;  System.out.println('Element at index '+   index + ' is '+   getSum(index));  // Add 2 to all the   // element from [03]  l = 0; r = 3; val = 4;  update(l r n val);  // Find the element  // at Index 3  index = 3;  System.out.println('Element at index '+   index + ' is '+   getSum(index));  } } // This code is contributed // by Puneet Kumar. 

# Python3 code to demonstrate Range Update and # PoQueries on a Binary Index Tree # Updates a node in Binary Index Tree (BITree) at given index # in BITree. The given value 'val' is added to BITree[i] and # all of its ancestors in tree. def updateBIT(BITree n index val): # index in BITree[] is 1 more than the index in arr[] index = index + 1 # Traverse all ancestors and add 'val' while (index <= n): # Add 'val' to current node of BI Tree BITree[index] += val # Update index to that of parent in update View index += index & (-index) # Constructs and returns a Binary Indexed Tree for given # array of size n. def constructBITree(arr n): # Create and initialize BITree[] as 0 BITree = [0]*(n+1) # Store the actual values in BITree[] using update() for i in range(n): updateBIT(BITree n i arr[i]) return BITree # SERVES THE PURPOSE OF getElement() # Returns sum of arr[0..index]. This function assumes # that the array is preprocessed and partial sums of # array elements are stored in BITree[] def getSum(BITree index): sum = 0 # Initialize result # index in BITree[] is 1 more than the index in arr[] index = index + 1 # Traverse ancestors of BITree[index] while (index > 0): # Add current element of BITree to sum sum += BITree[index] # Move index to parent node in getSum View index -= index & (-index) return sum # Updates such that getElement() gets an increased # value when queried from l to r. def update(BITree l r n val): # Increase value at 'l' by 'val' updateBIT(BITree n l val) # Decrease value at 'r+1' by 'val' updateBIT(BITree n r+1 -val) # Driver code arr = [0 0 0 0 0] n = len(arr) BITree = constructBITree(arr n) # Add 2 to all the element from [24] l = 2 r = 4 val = 2 update(BITree l r n val) # Find the element at Index 4 index = 4 print('Element at index' index 'is' getSum(BITree index)) # Add 2 to all the element from [03] l = 0 r = 3 val = 4 update(BITree l r n val) # Find the element at Index 3 index = 3 print('Element at index' index 'is' getSum(BITreeindex)) # This code is contributed by mohit kumar 29 

using System; /* C# code to demonstrate Range Update and  * Point Queries on a Binary Index Tree.  * This method only works when all array  * values are initially 0.*/ public class GFG {  // Max tree size   public const int MAX = 1000;  public static int[] BITree = new int[MAX];  // Updates a node in Binary Index   // Tree (BITree) at given index   // in BITree. The given value 'val'   // is added to BITree[i] and   // all of its ancestors in tree.   public static void updateBIT(int n int index int val)  {  // index in BITree[] is 1   // more than the index in arr[]   index = index + 1;  // Traverse all ancestors   // and add 'val'   while (index <= n)  {  // Add 'val' to current   // node of BITree   BITree[index] += val;  // Update index to that   // of parent in update View   index += index & (-index);  }  }  // Constructs Binary Indexed Tree   // for given array of size n.   public static void constructBITree(int[] arr int n)  {  // Initialize BITree[] as 0   for (int i = 1; i <= n; i++)  {  BITree[i] = 0;  }  // Store the actual values   // in BITree[] using update()   for (int i = 0; i < n; i++)  {  updateBIT(n i arr[i]);  }  // Uncomment below lines to   // see contents of BITree[]   // for (int i=1; i<=n; i++)   // cout << BITree[i] << ' ';   }  // SERVES THE PURPOSE OF getElement()   // Returns sum of arr[0..index]. This   // function assumes that the array is   // preprocessed and partial sums of   // array elements are stored in BITree[]   public static int getSum(int index)  {  int sum = 0; //Initialize result  // index in BITree[] is 1 more   // than the index in arr[]   index = index + 1;  // Traverse ancestors   // of BITree[index]   while (index > 0)  {  // Add current element   // of BITree to sum   sum += BITree[index];  // Move index to parent   // node in getSum View   index -= index & (-index);  }  // Return the sum   return sum;  }  // Updates such that getElement()   // gets an increased value when   // queried from l to r.   public static void update(int l int r int n int val)  {  // Increase value at   // 'l' by 'val'   updateBIT(n l val);  // Decrease value at   // 'r+1' by 'val'   updateBIT(n r + 1 -val);  }  // Driver Code   public static void Main(string[] args)  {  int[] arr = new int[] {0 0 0 0 0};  int n = arr.Length;  constructBITree(arrn);  // Add 2 to all the   // element from [24]   int l = 2 r = 4 val = 2;  update(l r n val);  int index = 4;  Console.WriteLine('Element at index ' + index + ' is ' + getSum(index));  // Add 2 to all the   // element from [03]   l = 0;  r = 3;  val = 4;  update(l r n val);  // Find the element   // at Index 3   index = 3;  Console.WriteLine('Element at index ' + index + ' is ' + getSum(index));  } }  // This code is contributed by Shrikant13 

// Updates a node in Binary Index Tree (BITree) at given index // in BITree. The given value 'val' is added to BITree[i] and // all of its ancestors in tree. function updateBIT(BITree n index val) {  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;  // Traverse all ancestors and add 'val'  while (index <= n) {  // Add 'val' to current node of BI Tree  BITree[index] += val;  // Update index to that of parent in update View  index += index & (-index);  } } // Constructs and returns a Binary Indexed Tree for given // array of size n. function constructBITree(arr n) {  // Create and initialize BITree[] as 0  let BITree = new Array(n+1).fill(0);  // Store the actual values in BITree[] using update()  for (let i = 0; i < n; i++) {  updateBIT(BITree n i arr[i]);  }  return BITree; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] function getSum(BITree index) {  let sum = 0; // Initialize result  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;  // Traverse ancestors of BITree[index]  while (index > 0) {  // Add current element of BITree to sum  sum += BITree[index];  // Move index to parent node in getSum View  index -= index & (-index);  }  return sum; } // Updates such that getElement() gets an increased // value when queried from l to r. function update(BITree l r n val) {  // Increase value at 'l' by 'val'  updateBIT(BITree n l val);  // Decrease value at 'r+1' by 'val'  updateBIT(BITree n r+1 -val); } // Test the functions let arr = [0 0 0 0 0]; let n = arr.length; let BITree = constructBITree(arr n); // Add 2 to all the element from [24] let l = 2 r = 4 val = 2; update(BITree l r n val); // Find the element at Index 4 let index = 4; console.log(`Element at index ${index} is ${getSum(BITreeindex)}`); // Add 2 to all the element from [03] l = 0 r = 3 val = 4; update(BITree l r n val); // Find the element at Index 3 index = 3; console.log(`Element at index ${index} is ${getSum(BITreeindex)}`);