Gitt en matrise arr[0..n-1]. Følgende operasjoner må utføres.
Til å begynne med er alle elementene i matrisen 0. Forespørsler kan være i hvilken som helst rekkefølge, dvs. det kan være mange oppdateringer før punktspørring.
Eksempel:
manuell testing
Input: arr = {0 0 0 0 0} Queries: update : l = 0 r = 4 val = 2 getElement : i = 3 update : l = 3 r = 4 val = 3 getElement : i = 3 Output: Element at 3 is 2 Element at 3 is 5 Explanation: Array after first update becomes {2 2 2 2 2} Array after second update becomes {2 2 2 5 5}Metode 1 [oppdatering : O(n) getElement() : O(1)]
Tidskompleksiteten i verste fall er O(q*n) der q er antall spørringer og n er antall elementer.
Metode 2 [oppdatering: O(1) getElement(): O(n)]
Vi kan unngå å oppdatere alle elementer og kan bare oppdatere 2 indekser av matrisen!
abstrakt klasse java
arr[l] = arr[l] + val arr[r+1] = arr[r+1] - val
La oss analysere oppdateringsspørringen. Hvorfor legge til val til lthindeks? Legger til verdi til lthindeks betyr at alle elementene etter l økes med val siden vi skal beregne prefikssummen for hvert element. Hvorfor trekke fra val fra (r+1)thindeks? En områdeoppdatering var nødvendig fra [lr], men det vi har oppdatert er [l n-1], så vi må fjerne val fra alle elementene etter r, dvs. trekke fra val fra (r+1)thindeks. Dermed legges verdien til området [lr]. Nedenfor er implementeringen av tilnærmingen ovenfor.
C++
// C++ program to demonstrate Range Update // and Point Queries Without using BIT #include
// 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
Produksjon:
Element at index 4 is 2 Element at index 3 is 6
Tidskompleksitet : O(q*n) hvor q er antall spørringer.
Hjelpeplass: På)
Metode 3 (ved bruk av binært indeksert tre)
I metode 2 har vi sett at problemet kan reduseres til oppdatering og prefikssumspørringer. Det har vi sett BIT kan brukes til å gjøre oppdaterings- og prefikssumspørringer i O(Logn)-tid. Nedenfor er gjennomføringen.
C++// C++ code to demonstrate Range Update and // Point Queries on a Binary Index Tree #include
/* 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)}`);
Produksjon:
Element at index 4 is 2 Element at index 3 is 6
Tidskompleksitet: O(q * log n) + O(n * log n) hvor q er antall spørringer.
eks av brukernavn
Hjelpeplass: På)
Metode 1 er effektiv når de fleste spørringene er getElement() metode 2 er effektiv når de fleste spørringene er oppdateringer() og metode 3 foretrekkes når det er en blanding av begge spørringene.