計數和切換二進制數組上的查詢 · GeeksForGeeks 中文系列教程

# 計數和切換二進制數組上的查詢 > 原文： [https://www.geeksforgeeks.org/count-toggle-queries-binary-array/](https://www.geeksforgeeks.org/count-toggle-queries-binary-array/) 給定大小 n，其中最初所有元素均為 0。任務是執行以下兩種類型的多個查詢。查詢可以按任何順序出現。 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 range Output : Total number of 1's in range 2 to 3 is = 1 Total number of 1's in range 1 to 4 is = 2 ``` 針對此問題的一種**簡單解決方案**是遍歷“切換”查詢的完整范圍，當您獲得“計數”查詢時，然后為給定范圍計算所有 1。但是這種方法的時間復雜度將是 O（q * n），其中 q =查詢總數。針對此問題的有效**解決方案是將[段樹](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)與 [**延遲傳播**](https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/) 結合使用。在這里，我們收集更新，直到獲得“ Count”查詢。當我們獲得“計數”的查詢時，我們會在數組中進行所有先前收集的 Toggle 更新，然后在給定范圍內對數字 1 進行計數。以下是上述方法的實現**： ## C++ ```cpp // 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 // 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 ```py # 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# ```cs // 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*/ ``` **輸出**： ``` 1 2 ``` 本文由 [**Shashank Mishra（Gullu）**](https://practice.geeksforgeeks.org/user-profile.php?user=Shashank%20Mishra) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，您還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。