给定一个大小n，其中最初所有元素均为0。任务是执行以下两种类型的多个查询。查询可以以任何顺序出现。
null
1.切换（开始、结束）： 切换（0到1或1到0）从“开始”到“结束”的值。
2.计数（开始、结束）： 计算从“开始”到“结束”的给定范围内的1个数。
Input : n = 5 // we have n = 5 blocks toggle 1 2 // change 1 into 0 or 0 into 1 Toggle 2 4 Count 2 3 // count all 1's within the range Toggle 2 4 Count 1 4 // count all 1's within the rangeOutput : Total number of 1's in range 2 to 3 is = 1 Total number of 1's in range 1 to 4 is = 2
A. 简单解决方案 对于这个问题，需要遍历“Toggle”查询的整个范围，当您得到“Count”查询时，然后对给定范围的所有1进行计数。但是这种方法的时间复杂度是O（q*n），其中q=查询总数。 一 有效率的 解决这个问题的方法是使用 分段树 具有 惰性传播 .在这里，我们收集更新，直到我们得到一个“计数”查询。当我们得到“Count”的查询时，我们在数组中进行之前收集的所有切换更新，然后在给定范围内计算1的数量。 以下是上述方法的实施情况：
C++
// C++ program to implement toggle and count // queries on a binary array. #include<bits/stdc++.h> using namespace std; const int MAX = 100000; // segment tree to store count of 1's within range int tree[MAX] = {0}; // bool type tree to collect the updates for toggling // the values of 1 and 0 in given range bool lazy[MAX] = { false }; // function for collecting updates of toggling // node --> index of current node in segment tree // st --> starting index of current node // en --> ending index of current node // us --> starting index of range update query // ue --> ending index of range update query void toggle( int node, int st, int en, int us, int ue) { // If lazy value is non-zero for current node of segment // tree, then there are some pending updates. So we need // to make sure that the pending updates are done before // making new updates. Because this value may be used by // parent after recursive calls (See last line of this // function) if (lazy[node]) { // Make pending updates using value stored in lazy nodes lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node because if // it is leaf node then we cannot go further if (st < en) { // We can postpone updating children we don't // need their new values now. // Since we are not yet updating children of 'node', // we need to set lazy flags for the children lazy[node<<1] = !lazy[node<<1]; lazy[1+(node<<1)] = !lazy[1+(node<<1)]; } } // out of range if (st>en || us > en || ue < st) return ; // Current segment is fully in range if (us<=st && en<=ue) { // Add the difference to current node tree[node] = en-st+1 - tree[node]; // same logic for checking leaf node or not if (st < en) { // This is where we store values in lazy nodes, // rather than updating the segment tree itelf // Since we don't need these updated values now // we postpone updates by storing values in lazy[] lazy[node<<1] = !lazy[node<<1]; lazy[1+(node<<1)] = !lazy[1+(node<<1)]; } return ; } // If not completely in rang, but overlaps, recur for // children, int mid = (st+en)/2; toggle((node<<1), st, mid, us, ue); toggle((node<<1)+1, mid+1,en, us, ue); // And use the result of children calls to update this node if (st < en) tree[node] = tree[node<<1] + tree[(node<<1)+1]; } /* node --> Index of current node in the segment tree. Initially 0 is passed as root is always at' index 0 st & en --> Starting and ending indexes of the segment represented by current node, i.e., tree[node] qs & qe --> Starting and ending indexes of query range */ // function to count number of 1's within given range int countQuery( int node, int st, int en, int qs, int qe) { // current node is out of range if (st>en || qs > en || qe < st) return 0; // If lazy flag is set for current node of segment tree, // then there are some pending updates. So we need to // make sure that the pending updates are done before // processing the sub sum query if (lazy[node]) { // Make pending updates to this node. Note that this // node represents sum of elements in arr[st..en] and // all these elements must be increased by lazy[node] lazy[node] = false ; tree[node] = en-st+1-tree[node]; // checking if it is not leaf node because if // it is leaf node then we cannot go further if (st<en) { // Since we are not yet updating children os si, // we need to set lazy values for the children lazy[node<<1] = !lazy[node<<1]; lazy[(node<<1)+1] = !lazy[(node<<1)+1]; } } // At this point we are sure that pending lazy updates // are done for current node. So we can return value // If this segment lies in range if (qs<=st && en<=qe) return tree[node]; // If a part of this segment overlaps with the given range int mid = (st+en)/2; return countQuery((node<<1), st, mid, qs, qe) + countQuery((node<<1)+1, mid+1, en, qs, qe); } // Driver program to run the case int main() { int n = 5; toggle(1, 0, n-1, 1, 2); // Toggle 1 2 toggle(1, 0, n-1, 2, 4); // Toggle 2 4 cout << countQuery(1, 0, n-1, 2, 3) << endl; // Count 2 3 toggle(1, 0, n-1, 2, 4); // Toggle 2 4 cout << countQuery(1, 0, n-1, 1, 4) << endl; // Count 1 4 return 0; } |
JAVA
// Java program to implement toggle and // count queries on a binary array. class GFG { static final int MAX = 100000 ; // segment tree to store count // of 1's within range static int tree[] = new int [MAX]; // bool type tree to collect the updates // for toggling the values of 1 and 0 in // given range static boolean lazy[] = new boolean [MAX]; // function for collecting updates of toggling // node --> index of current node in segment tree // st --> starting index of current node // en --> ending index of current node // us --> starting index of range update query // ue --> ending index of range update query static void toggle( int node, int st, int en, int us, int ue) { // If lazy value is non-zero for current // node of segment tree, then there are // some pending updates. So we need // to make sure that the pending updates // are done before making new updates. // Because this value may be used by // parent after recursive calls (See last // line of this function) if (lazy[node]) { // Make pending updates using value // stored in lazy nodes lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (st < en) { // We can postpone updating children // we don't need their new values now. // Since we are not yet updating children // of 'node', we need to set lazy flags // for the children lazy[node << 1 ] = !lazy[node << 1 ]; lazy[ 1 + (node << 1 )] = !lazy[ 1 + (node << 1 )]; } } // out of range if (st > en || us > en || ue < st) { return ; } // Current segment is fully in range if (us <= st && en <= ue) { // Add the difference to current node tree[node] = en - st + 1 - tree[node]; // same logic for checking leaf node or not if (st < en) { // This is where we store values in lazy nodes, // rather than updating the segment tree itelf // Since we don't need these updated values now // we postpone updates by storing values in lazy[] lazy[node << 1 ] = !lazy[node << 1 ]; lazy[ 1 + (node << 1 )] = !lazy[ 1 + (node << 1 )]; } return ; } // If not completely in rang, // but overlaps, recur for children, int mid = (st + en) / 2 ; toggle((node << 1 ), st, mid, us, ue); toggle((node << 1 ) + 1 , mid + 1 , en, us, ue); // And use the result of children // calls to update this node if (st < en) { tree[node] = tree[node << 1 ] + tree[(node << 1 ) + 1 ]; } } /* node --> Index of current node in the segment tree. Initially 0 is passed as root is always at' index 0 st & en --> Starting and ending indexes of the segment represented by current node, i.e., tree[node] qs & qe --> Starting and ending indexes of query range */ // function to count number of 1's // within given range static int countQuery( int node, int st, int en, int qs, int qe) { // current node is out of range if (st > en || qs > en || qe < st) { return 0 ; } // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before processing // the sub sum query if (lazy[node]) { // Make pending updates to this node. // Note that this node represents sum // of elements in arr[st..en] and // all these elements must be increased // by lazy[node] lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node because if // it is leaf node then we cannot go further if (st < en) { // Since we are not yet updating children os si, // we need to set lazy values for the children lazy[node << 1 ] = !lazy[node << 1 ]; lazy[(node << 1 ) + 1 ] = !lazy[(node << 1 ) + 1 ]; } } // At this point we are sure that pending // lazy updates are done for current node. // So we can return value If this segment // lies in range if (qs <= st && en <= qe) { return tree[node]; } // If a part of this segment overlaps // with the given range int mid = (st + en) / 2 ; return countQuery((node << 1 ), st, mid, qs, qe) + countQuery((node << 1 ) + 1 , mid + 1 , en, qs, qe); } // Driver Code public static void main(String args[]) { int n = 5 ; toggle( 1 , 0 , n - 1 , 1 , 2 ); // Toggle 1 2 toggle( 1 , 0 , n - 1 , 2 , 4 ); // Toggle 2 4 System.out.println(countQuery( 1 , 0 , n - 1 , 2 , 3 )); // Count 2 3 toggle( 1 , 0 , n - 1 , 2 , 4 ); // Toggle 2 4 System.out.println(countQuery( 1 , 0 , n - 1 , 1 , 4 )); // Count 1 4 } } // This code is contributed by 29AjayKumar |
Python3
# Python program to implement toggle and count # queries on a binary array. MAX = 100000 # segment tree to store count of 1's within range tree = [ 0 ] * MAX # bool type tree to collect the updates for toggling # the values of 1 and 0 in given range lazy = [ False ] * MAX # function for collecting updates of toggling # node --> index of current node in segment tree # st --> starting index of current node # en --> ending index of current node # us --> starting index of range update query # ue --> ending index of range update query def toggle(node: int , st: int , en: int , us: int , ue: int ): # If lazy value is non-zero for current node of segment # tree, then there are some pending updates. So we need # to make sure that the pending updates are done before # making new updates. Because this value may be used by # parent after recursive calls (See last line of this # function) if lazy[node]: # Make pending updates using value stored in lazy nodes lazy[node] = False tree[node] = en - st + 1 - tree[node] # checking if it is not leaf node because if # it is leaf node then we cannot go further if st < en: # We can postpone updating children we don't # need their new values now. # Since we are not yet updating children of 'node', # we need to set lazy flags for the children lazy[node << 1 ] = not lazy[node << 1 ] lazy[ 1 + (node << 1 )] = not lazy[ 1 + (node << 1 )] # out of range if st > en or us > en or ue < st: return # Current segment is fully in range if us < = st and en < = ue: # Add the difference to current node tree[node] = en - st + 1 - tree[node] # same logic for checking leaf node or not if st < en: # This is where we store values in lazy nodes, # rather than updating the segment tree itelf # Since we don't need these updated values now # we postpone updates by storing values in lazy[] lazy[node << 1 ] = not lazy[node << 1 ] lazy[ 1 + (node << 1 )] = not lazy[ 1 + (node << 1 )] return # If not completely in rang, but overlaps, recur for # children, mid = (st + en) / / 2 toggle((node << 1 ), st, mid, us, ue) toggle((node << 1 ) + 1 , mid + 1 , en, us, ue) # And use the result of children calls to update this node if st < en: tree[node] = tree[node << 1 ] + tree[(node << 1 ) + 1 ] # node --> Index of current node in the segment tree. # Initially 0 is passed as root is always at' # index 0 # st & en --> Starting and ending indexes of the # segment represented by current node, # i.e., tree[node] # qs & qe --> Starting and ending indexes of query # range # function to count number of 1's within given range def countQuery(node: int , st: int , en: int , qs: int , qe: int ) - > int : # current node is out of range if st > en or qs > en or qe < st: return 0 # If lazy flag is set for current node of segment tree, # then there are some pending updates. So we need to # make sure that the pending updates are done before # processing the sub sum query if lazy[node]: # Make pending updates to this node. Note that this # node represents sum of elements in arr[st..en] and # all these elements must be increased by lazy[node] lazy[node] = False tree[node] = en - st + 1 - tree[node] # checking if it is not leaf node because if # it is leaf node then we cannot go further if st < en: # Since we are not yet updating children os si, # we need to set lazy values for the children lazy[node << 1 ] = not lazy[node << 1 ] lazy[(node << 1 ) + 1 ] = not lazy[(node << 1 ) + 1 ] # At this point we are sure that pending lazy updates # are done for current node. So we can return value # If this segment lies in range if qs < = st and en < = qe: return tree[node] # If a part of this segment overlaps with the given range mid = (st + en) / / 2 return countQuery((node << 1 ), st, mid, qs, qe) + countQuery( (node << 1 ) + 1 , mid + 1 , en, qs, qe) # Driver Code if __name__ = = "__main__" : n = 5 toggle( 1 , 0 , n - 1 , 1 , 2 ) # Toggle 1 2 toggle( 1 , 0 , n - 1 , 2 , 4 ) # Toggle 2 4 print (countQuery( 1 , 0 , n - 1 , 2 , 3 )) # count 2 3 toggle( 1 , 0 , n - 1 , 2 , 4 ) # Toggle 2 4 print (countQuery( 1 , 0 , n - 1 , 1 , 4 )) # count 1 4 # This code is contributed by # sanjeev2552 |
C#
// C# program to implement toggle and // count queries on a binary array. using System; public class GFG{ static readonly int MAX = 100000; // segment tree to store count // of 1's within range static int []tree = new int [MAX]; // bool type tree to collect the updates // for toggling the values of 1 and 0 in // given range static bool []lazy = new bool [MAX]; // function for collecting updates of toggling // node --> index of current node in segment tree // st --> starting index of current node // en --> ending index of current node // us --> starting index of range update query // ue --> ending index of range update query static void toggle( int node, int st, int en, int us, int ue) { // If lazy value is non-zero for current // node of segment tree, then there are // some pending updates. So we need // to make sure that the pending updates // are done before making new updates. // Because this value may be used by // parent after recursive calls (See last // line of this function) if (lazy[node]) { // Make pending updates using value // stored in lazy nodes lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (st < en) { // We can postpone updating children // we don't need their new values now. // Since we are not yet updating children // of 'node', we need to set lazy flags // for the children lazy[node << 1] = !lazy[node << 1]; lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; } } // out of range if (st > en || us > en || ue < st) { return ; } // Current segment is fully in range if (us <= st && en <= ue) { // Add the difference to current node tree[node] = en - st + 1 - tree[node]; // same logic for checking leaf node or not if (st < en) { // This is where we store values in lazy nodes, // rather than updating the segment tree itelf // Since we don't need these updated values now // we postpone updates by storing values in lazy[] lazy[node << 1] = !lazy[node << 1]; lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; } return ; } // If not completely in rang, // but overlaps, recur for children, int mid = (st + en) / 2; toggle((node << 1), st, mid, us, ue); toggle((node << 1) + 1, mid + 1, en, us, ue); // And use the result of children // calls to update this node if (st < en) { tree[node] = tree[node << 1] + tree[(node << 1) + 1]; } } /* node --> Index of current node in the segment tree. Initially 0 is passed as root is always at' index 0 st & en --> Starting and ending indexes of the segment represented by current node, i.e., tree[node] qs & qe --> Starting and ending indexes of query range */ // function to count number of 1's // within given range static int countQuery( int node, int st, int en, int qs, int qe) { // current node is out of range if (st > en || qs > en || qe < st) { return 0; } // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before processing // the sub sum query if (lazy[node]) { // Make pending updates to this node. // Note that this node represents sum // of elements in arr[st..en] and // all these elements must be increased // by lazy[node] lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node because if // it is leaf node then we cannot go further if (st < en) { // Since we are not yet updating children os si, // we need to set lazy values for the children lazy[node << 1] = !lazy[node << 1]; lazy[(node << 1) + 1] = !lazy[(node << 1) + 1]; } } // At this point we are sure that pending // lazy updates are done for current node. // So we can return value If this segment // lies in range if (qs <= st && en <= qe) { return tree[node]; } // If a part of this segment overlaps // with the given range int mid = (st + en) / 2; return countQuery((node << 1), st, mid, qs, qe) + countQuery((node << 1) + 1, mid + 1, en, qs, qe); } // Driver Code public static void Main() { int n = 5; toggle(1, 0, n - 1, 1, 2); // Toggle 1 2 toggle(1, 0, n - 1, 2, 4); // Toggle 2 4 Console.WriteLine(countQuery(1, 0, n - 1, 2, 3)); // Count 2 3 toggle(1, 0, n - 1, 2, 4); // Toggle 2 4 Console.WriteLine(countQuery(1, 0, n - 1, 1, 4)); // Count 1 4 } } /*This code is contributed by PrinciRaj1992*/ |
Javascript
<script> // JavaScript program to implement toggle and // count queries on a binary array. let MAX = 100000; // segment tree to store count // of 1's within range let tree= new Array(MAX); // bool type tree to collect the updates // for toggling the values of 1 and 0 in // given range let lazy = new Array(MAX); for (let i=0;i<MAX;i++) { tree[i]=0; lazy[i]= false ; } // function for collecting updates of toggling // node --> index of current node in segment tree // st --> starting index of current node // en --> ending index of current node // us --> starting index of range update query // ue --> ending index of range update query function toggle(node,st,en,us,ue) { // If lazy value is non-zero for current // node of segment tree, then there are // some pending updates. So we need // to make sure that the pending updates // are done before making new updates. // Because this value may be used by // parent after recursive calls (See last // line of this function) if (lazy[node]) { // Make pending updates using value // stored in lazy nodes lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node // because if it is leaf node then // we cannot go further if (st < en) { // We can postpone updating children // we don't need their new values now. // Since we are not yet updating children // of 'node', we need to set lazy flags // for the children lazy[node << 1] = !lazy[node << 1]; lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; } } // out of range if (st > en || us > en || ue < st) { return ; } // Current segment is fully in range if (us <= st && en <= ue) { // Add the difference to current node tree[node] = en - st + 1 - tree[node]; // same logic for checking leaf node or not if (st < en) { // This is where we store values in lazy nodes, // rather than updating the segment tree itelf // Since we don't need these updated values now // we postpone updates by storing values in lazy[] lazy[node << 1] = !lazy[node << 1]; lazy[1 + (node << 1)] = !lazy[1 + (node << 1)]; } return ; } // If not completely in rang, // but overlaps, recur for children, let mid = Math.floor((st + en) / 2); toggle((node << 1), st, mid, us, ue); toggle((node << 1) + 1, mid + 1, en, us, ue); // And use the result of children // calls to update this node if (st < en) { tree[node] = tree[node << 1] + tree[(node << 1) + 1]; } } /* node --> Index of current node in the segment tree. Initially 0 is passed as root is always at' index 0 st & en --> Starting and ending indexes of the segment represented by current node, i.e., tree[node] qs & qe --> Starting and ending indexes of query range */ // function to count number of 1's // within given range function countQuery(node,st,en,qs,qe) { // current node is out of range if (st > en || qs > en || qe < st) { return 0; } // If lazy flag is set for current // node of segment tree, then there // are some pending updates. So we // need to make sure that the pending // updates are done before processing // the sub sum query if (lazy[node]) { // Make pending updates to this node. // Note that this node represents sum // of elements in arr[st..en] and // all these elements must be increased // by lazy[node] lazy[node] = false ; tree[node] = en - st + 1 - tree[node]; // checking if it is not leaf node because if // it is leaf node then we cannot go further if (st < en) { // Since we are not yet updating children os si, // we need to set lazy values for the children lazy[node << 1] = !lazy[node << 1]; lazy[(node << 1) + 1] = !lazy[(node << 1) + 1]; } } // At this point we are sure that pending // lazy updates are done for current node. // So we can return value If this segment // lies in range if (qs <= st && en <= qe) { return tree[node]; } // If a part of this segment overlaps // with the given range let mid = Math.floor((st + en) / 2); return countQuery((node << 1), st, mid, qs, qe) + countQuery((node << 1) + 1, mid + 1, en, qs, qe); } // Driver Code let n = 5; toggle(1, 0, n - 1, 1, 2); // Toggle 1 2 toggle(1, 0, n - 1, 2, 4); // Toggle 2 4 document.write(countQuery(1, 0, n - 1, 2, 3)+ "<br>" ); // Count 2 3 toggle(1, 0, n - 1, 2, 4); // Toggle 2 4 document.write(countQuery(1, 0, n - 1, 1, 4)+ "<br>" ); // Count 1 4 // This code is contributed by rag2127 </script> |
输出：
12
本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
