Binary Indexed Tree : Range Updates and Point Queries | C ++ 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 . ; Get the element indexed at i ; To get ith element sum of all the elements from 0 to i need to be computed ; Driver program to test above function ; Find the element at Index 4 ; Find the element at Index 3
#include <bits/stdc++.h> NEW_LINE using namespace std ; void update ( int arr [ ] , int l , int r , int val ) { arr [ l ] += val ; arr [ r + 1 ] -= val ; } int getElement ( int arr [ ] , int i ) { int res = 0 ; for ( int j = 0 ; j <= i ; j ++ ) res += arr [ j ] ; return res ; } 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 ) ; int index = 4 ; cout << " Element ▁ at ▁ index ▁ " << index << " ▁ is ▁ " << getElement ( arr , index ) << endl ; l = 0 , r = 3 , val = 4 ; update ( arr , l , r , val ) ; index = 3 ; cout << " Element ▁ at ▁ index ▁ " << index << " ▁ is ▁ " << getElement ( arr , index ) << endl ; return 0 ; }