让我们考虑下面的问题来理解片段树。 我们有一个数组arr[0…n-1]。我们应该能够 1求从索引l到r的元素的异或，其中0<=l<=r<=n-1。 2.将数组中指定元素的值更改为新值x。我们需要执行arr[i]=x，其中0<=i<=n-1。 类似 给定范围的和。
null
一个简单的解决方案 就是从l到r运行一个循环，并计算给定范围内元素的xor。要更新一个值，只需执行arr[i]=x。第一个操作需要O（n）时间，第二个操作需要O（1）时间。 有效方法： 如果查询和更新的数量相等，我们可以在O（logn）时间内执行这两个操作。我们可以使用段树在O（Logn）时间内完成这两个操作。 分段树的表示 1.叶节点是输入数组的元素。 2.每个内部节点代表叶节点的一些合并。对于不同的问题，合并可能会有所不同。对于这个问题，合并是节点下叶子的异或。 树的数组表示用于表示段树。对于索引i处的每个节点，左子节点位于索引2*i+1处，右子节点位于索引2*i+2处，父节点位于（i-1）/2处。
查询给定范围的产品 一旦构建了树，如何使用构建的段树获取Xor。下面是获取元素异或的算法。
int getXor(node, l, r) { if range of node is within l and r return value in node else if range of node is completely outside l and r return 0 else return getXor(node's left child, l, r) ^ getXor(node's right child, l, r)}
C++
// C++ program to show segment tree operations // like construction, query and update #include <bits/stdc++.h> #include <math.h> using namespace std; // A utility function to get the middle // index from corner indexes. int getMid( int s, int e) { return s + (e - s)/2; } /* A recursive function to get the Xor of values in given range of the array. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0. ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[si] qs & qe --> Starting and ending indexes of query range */ int getXorUtil( int *st, int ss, int se, int qs, int qe, int si) { // If segment of this node is a part of given // range, then return the Xor of the segment if (qs <= ss && qe >= se) return st[si]; // If segment of this node is outside // the given range if (se < qs || ss > qe) return 0; // If a part of this segment overlaps // with the given range int mid = getMid(ss, se); return getXorUtil(st, ss, mid, qs, qe, 2*si+1) ^ getXorUtil(st, mid+1, se, qs, qe, 2*si+2); } /* A recursive function to update the nodes which have the given index in their range. The following are parameters st, si, ss and se are same as getXorUtil() i --> index of the element to be updated. This index is in input array.*/ void updateValueUtil( int *st, int ss, int se, int i, int prev_val, int new_val, int si) { // Base Case: If the input index lies outside // the range of this segment if (i < ss || i > se) return ; // If the input index is in range of this node, // then update the value of the node and its children st[si] = (st[si]^prev_val)^new_val; if (se != ss) { int mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, prev_val, new_val, 2*si + 1); updateValueUtil(st, mid+1, se, i, prev_val, new_val, 2*si + 2); } } // The function to update a value in input // array and segment tree. It uses updateValueUtil() // to update the value in segment tree void updateValue( int arr[], int *st, int n, int i, int new_val) { // Check for erroneous input index if (i < 0 || i > n-1) { printf ( "Invalid Input" ); return ; } int temp = arr[i]; // Update the value in array arr[i] = new_val; // Update the values of nodes in segment tree updateValueUtil(st, 0, n-1, i, temp, new_val, 0); } // Return Xor of elements in range from index qs (query start) // to qe (query end). It mainly uses getXorUtil() int getXor( int *st, int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n-1 || qs > qe) { printf ( "Invalid Input" ); return 0; } return getXorUtil(st, 0, n-1, qs, qe, 0); } // A recursive function that constructs // Segment Tree for array[ss..se]. si is // index of current node in segment tree st int constructSTUtil( int arr[], int ss, int se, int *st, int si) { // If there is one element in array, // store it in current node of segment // tree and return if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // If there are more than one elements, // then recur for left and right subtrees // and store the Xor of values in this node int mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) ^ constructSTUtil(arr, mid+1, se, st, si*2+2); return st[si]; } /* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */ int *constructST( int arr[], int n) { // Allocate memory for segment tree // Height of segment tree int x = ( int )( ceil (log2(n))); // Maximum size of segment tree int max_size = 2*( int ) pow (2, x) - 1; // Allocate memory int *st = new int [max_size]; // Fill the allocated memory st constructSTUtil(arr, 0, n-1, st, 0); // Return the constructed segment tree return st; } // Driver program to test above functions int main() { int arr[] = {1, 3, 5, 7, 9, 11}; int n = sizeof (arr)/ sizeof (arr[0]); // Build segment tree from given array int *st = constructST(arr, n); // Print Xor of values in array from index 1 to 3 printf ( "Xor of values in given range = %d" , getXor(st, n, 0, 2)); // Update: set arr[1] = 10 and update corresponding // segment tree nodes updateValue(arr, st, n, 1, 10); // Find Xor after the value is updated printf ( "Updated Xor of values in given range = %d" , getXor(st, n, 0, 2)); return 0; } |
JAVA
// Java implementation of the approach import java.util.*; class GFG { // A utility function to get the middle // index from corner indexes. static int getMid( int s, int e) { return s + (e - s) / 2 ; } /* * A recursive function to get the Xor of * values in given range of the array. The * following are parameters for this function. * st --> Pointer to segment tree * si --> Index of current node in the segment tree. * Initially 0 is passed as root is always * at index 0. * ss & se --> Starting and ending indexes of * the segment represented by current * node, i.e., st[si] * qs & qe --> Starting and ending indexes of * query range */ static int getXorUtil( int [] st, int ss, int se, int qs, int qe, int si) { // If segment of this node is a part of given // range, then return the Xor of the segment if (qs <= ss && qe >= se) return st[si]; // If segment of this node is outside // the given range if (se < qs || ss > qe) return 0 ; // If a part of this segment overlaps // with the given range int mid = getMid(ss, se); return getXorUtil(st, ss, mid, qs, qe, 2 * si + 1 ) ^ getXorUtil(st, mid + 1 , se, qs, qe, 2 * si + 2 ); } /* * A recursive function to update the nodes * which have the given index in their range. * The following are parameters * st, si, ss and se are same as getXorUtil() * i --> index of the element to be updated. * This index is in input array. */ static void updateValueUtil( int [] st, int ss, int se, int i, int prev_val, int new_val, int si) { // Base Case: If the input index lies outside // the range of this segment if (i < ss || i > se) return ; // If the input index is in range of this node, // then update the value of the node and its children st[si] = (st[si] ^ prev_val) ^ new_val; if (se != ss) { int mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, prev_val, new_val, 2 * si + 1 ); updateValueUtil(st, mid + 1 , se, i, prev_val, new_val, 2 * si + 2 ); } } // The function to update a value in input // array and segment tree. It uses updateValueUtil() // to update the value in segment tree static void updateValue( int arr[], int [] st, int n, int i, int new_val) { // Check for erroneous input index if (i < 0 || i > n - 1 ) { System.out.printf( "Invalid Input" ); return ; } int temp = arr[i]; // Update the value in array arr[i] = new_val; // Update the values of nodes in segment tree updateValueUtil(st, 0 , n - 1 , i, temp, new_val, 0 ); } // Return Xor of elements in range from index qs (query start) // to qe (query end). It mainly uses getXorUtil() static int getXor( int [] st, int n, int qs, int qe) { // Check for erroneous input values if (qs < 0 || qe > n - 1 || qs > qe) { System.out.printf( "Invalid Input" ); return 0 ; } return getXorUtil(st, 0 , n - 1 , qs, qe, 0 ); } // A recursive function that constructs // Segment Tree for array[ss..se]. si is // index of current node in segment tree st static int constructSTUtil( int arr[], int ss, int se, int [] st, int si) { // If there is one element in array, // store it in current node of segment // tree and return if (ss == se) { st[si] = arr[ss]; return arr[ss]; } // If there are more than one elements, // then recur for left and right subtrees // and store the Xor of values in this node int mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1 ) ^ constructSTUtil(arr, mid + 1 , se, st, si * 2 + 2 ); return st[si]; } /* * Function to construct segment tree from given array. * This function allocates memory for segment tree and * calls constructSTUtil() to fill the allocated memory */ static int [] constructST( int arr[], int n) { // Allocate memory for segment tree // Height of segment tree int x = ( int ) (Math.ceil(Math.log(n) / Math.log( 2 ))); // Maximum size of segment tree int max_size = 2 * ( int ) Math.pow( 2 , x) - 1 ; // Allocate memory int [] st = new int [max_size]; // Fill the allocated memory st constructSTUtil(arr, 0 , n - 1 , st, 0 ); // Return the constructed segment tree return st; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 3 , 5 , 7 , 9 , 11 }; int n = arr.length; // Build segment tree from given array int [] st = constructST(arr, n); // Print Xor of values in array from index 1 to 3 System.out.printf( "Xor of values in given range = %d" , getXor(st, n, 0 , 2 )); // Update: set arr[1] = 10 and update corresponding // segment tree nodes updateValue(arr, st, n, 1 , 10 ); // Find Xor after the value is updated System.out.printf( "Updated Xor of values in given range = %d" , getXor(st, n, 0 , 2 )); } } // This code is contributed by // sanjeev2552 |
Python3
# Python3 program to show segment tree operations # like construction, query and update from math import ceil, log2; # A utility function to get the middle # index from corner indexes. def getMid(s, e) : return s + (e - s) / / 2 ; """ A recursive function to get the Xor of values in given range of the array. The following are parameters for this function. st --> Pointer to segment tree si --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0. ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[si] qs & qe --> Starting and ending indexes of query range """ def getXorUtil(st, ss, se, qs, qe, si) : # If segment of this node is a part of given # range, then return the Xor of the segment if (qs < = ss and qe > = se) : return st[si]; # If segment of this node is outside # the given range if (se < qs or ss > qe) : return 0 ; # If a part of this segment overlaps # with the given range mid = getMid(ss, se); return getXorUtil(st, ss, mid, qs, qe, 2 * si + 1 ) ^ getXorUtil(st, mid + 1 , se, qs, qe, 2 * si + 2 ); """ A recursive function to update the nodes which have the given index in their range. The following are parameters st, si, ss and se are same as getXorUtil() i --> index of the element to be updated. This index is in input array.""" def updateValueUtil(st, ss, se, i, prev_val, new_val, si) : # Base Case: If the input index lies # outside the range of this segment if (i < ss or i > se) : return ; # If the input index is in range of this node, # then update the value of the node and its children st[si] = (st[si] ^ prev_val) ^ new_val; if (se ! = ss) : mid = getMid(ss, se); updateValueUtil(st, ss, mid, i, prev_val, new_val, 2 * si + 1 ); updateValueUtil(st, mid + 1 , se, i, prev_val, new_val, 2 * si + 2 ); # The function to update a value in input # array and segment tree. It uses updateValueUtil() # to update the value in segment tree def updateValue(arr, st, n, i, new_val) : # Check for erroneous input index if (i < 0 or i > n - 1 ) : print ( "Invalid Input" ); return ; temp = arr[i]; # Update the value in array arr[i] = new_val; # Update the values of nodes in segment tree updateValueUtil(st, 0 , n - 1 , i, temp, new_val, 0 ); # Return Xor of elements in range from # index qs (query start) to qe (query end). # It mainly uses getXorUtil() def getXor(st, n, qs, qe) : # Check for erroneous input values if (qs < 0 or qe > n - 1 or qs > qe) : print ( "Invalid Input" ); return 0 ; return getXorUtil(st, 0 , n - 1 , qs, qe, 0 ); # A recursive function that constructs # Segment Tree for array[ss..se]. si is # index of current node in segment tree st def constructSTUtil(arr, ss, se, st, si) : # If there is one element in array, # store it in current node of segment # tree and return if (ss = = se) : st[si] = arr[ss]; return arr[ss]; # If there are more than one elements, # then recur for left and right subtrees # and store the Xor of values in this node mid = getMid(ss, se); st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1 ) ^ constructSTUtil(arr, mid + 1 , se, st, si * 2 + 2 ); return st[si]; """ Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory """ def constructST(arr, n) : # Allocate memory for segment tree # Height of segment tree x = ( int )(ceil(log2(n))); # Maximum size of segment tree max_size = 2 * ( int )( 2 * * x) - 1 ; # Allocate memory st = [ 0 ] * (max_size); # Fill the allocated memory st constructSTUtil(arr, 0 , n - 1 , st, 0 ); # Return the constructed segment tree return st; # Driver Code if __name__ = = "__main__" : arr = [ 1 , 3 , 5 , 7 , 9 , 11 ]; n = len (arr); # Build segment tree from given array st = constructST(arr, n); # Print Xor of values in array from index 1 to 3 print ( "Xor of values in given range =" , getXor(st, n, 0 , 2 )); # Update: set arr[1] = 10 and update # corresponding segment tree nodes updateValue(arr, st, n, 1 , 10 ); # Find Xor after the value is updated print ( "Updated Xor of values in given range =" , getXor(st, n, 0 , 2 )); # This code is contributed by AnkitRai01 |
输出：
Xor of values in given range = 7Updated Xor of values in given range = 14
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
