{"id":6053,"date":"2020-01-05T10:23:01","date_gmt":"2020-01-05T18:23:01","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6053"},"modified":"2020-01-05T10:28:59","modified_gmt":"2020-01-05T18:28:59","slug":"leetcode-1310-xor-queries-of-a-subarray","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1310-xor-queries-of-a-subarray\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1310. XOR Queries of a Subarray"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1310. XOR Queries of a Subarray - \u5237\u9898\u627e\u5de5\u4f5c EP294\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/mCppc1CAshk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>Given the array&nbsp;<code>arr<\/code>&nbsp;of positive integers and the array&nbsp;<code>queries<\/code>&nbsp;where&nbsp;<code>queries[i] = [L<sub>i,&nbsp;<\/sub>R<sub>i<\/sub>]<\/code>,&nbsp;for each query&nbsp;<code>i<\/code>&nbsp;compute the&nbsp;<strong>XOR<\/strong>&nbsp;of elements from&nbsp;<code>L<sub>i<\/sub><\/code>&nbsp;to&nbsp;<code>Ri<\/code>&nbsp;(that is,&nbsp;<code>arr[L<sub>i<\/sub>]&nbsp;<strong>xor<\/strong>&nbsp;arr[L<sub>i+1<\/sub>]&nbsp;<strong>xor<\/strong>&nbsp;...&nbsp;<strong>xor<\/strong>&nbsp;arr[R<sub>i<\/sub>]<\/code>&nbsp;). Return an array containing the result for the given&nbsp;<code>queries<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]\n<strong>Output:<\/strong> [2,7,14,8] \n<strong>Explanation:<\/strong> \nThe binary representation of the elements in the array are:\n1 = 0001 \n3 = 0011 \n4 = 0100 \n8 = 1000 \nThe XOR values for queries are:\n[0,1] = 1 xor 3 = 2 \n[1,2] = 3 xor 4 = 7 \n[0,3] = 1 xor 3 xor 4 xor 8 = 14 \n[3,3] = 8\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]\n<strong>Output:<\/strong> [8,0,4,4]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= arr.length &lt;= 3 *&nbsp;10^4<\/code><\/li><li><code>1 &lt;= arr[i] &lt;= 10^9<\/code><\/li><li><code>1 &lt;= queries.length &lt;= 3 * 10^4<\/code><\/li><li><code>queries[i].length == 2<\/code><\/li><li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt; arr.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Prefix Sum<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1310-ep294.png\" alt=\"\" class=\"wp-image-6057\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1310-ep294.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1310-ep294-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1310-ep294-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(n) + O(q)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {\n    \/\/ xors[i + 1] = arr[0] ^ arr[1] ^ ... ^ arr[i]\n    vector<int> xors(arr.size() + 1);\n    for (int i = 0; i < arr.size(); ++i) {\n      xors[i + 1] = xors[i] ^ arr[i];\n    }\n    vector<int> ans;\n    for (const auto& q : queries) {\n      const int l = q[0];\n      const int r = q[1];\n      ans.push_back(xors[r + 1] ^ xors[l]);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>tby\n","protected":false},"excerpt":{"rendered":"<p>Given the array&nbsp;arr&nbsp;of positive integers and the array&nbsp;queries&nbsp;where&nbsp;queries[i] = [Li,&nbsp;Ri],&nbsp;for each query&nbsp;i&nbsp;compute the&nbsp;XOR&nbsp;of elements from&nbsp;Li&nbsp;to&nbsp;Ri&nbsp;(that is,&nbsp;arr[Li]&nbsp;xor&nbsp;arr[Li+1]&nbsp;xor&nbsp;&#8230;&nbsp;xor&nbsp;arr[Ri]&nbsp;). Return an array containing the result for the given&nbsp;queries.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[16,177,376,527,200,63],"class_list":["post-6053","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-bit","tag-medium","tag-on","tag-oq","tag-prefix-sum","tag-xor","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6053","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6053"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6053\/revisions"}],"predecessor-version":[{"id":6058,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6053\/revisions\/6058"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6053"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6053"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}