推 Che31128: 大師 09/13 22:32
推 sustainer123: 大師 09/13 22:33
推 dont: 大師 09/14 00:56
1310. XOR Queries of a Subarray
arr是一個正數矩陣
queries則是2D整數矩陣，其中queries[i]={left_i,right_i}
對每一個queries[i]請計算arr[left_i] xor arr[left_i+1] xor...xor arr[right_i]
請回傳最終結果
思路:
假設arr有n個元素
從arr[0]一直xor到arr[n-1]
並用一個prefix sum矩陣紀錄，prefix_sum[i]=arr[0] xor arr[1] xor ... xor arr[i]
如果要計算arr[i]~arr[j]的xor值就只要prefix_sum[j] ^ prefix_sum[i-1]就好
golang code：
func xorQueries(arr []int, queries [][]int) []int {
n, m := len(arr), len(queries)
xor_arr, res := make([]int, n+1), make([]int, m)
tmp := 0
for key, val := range arr {
tmp ^= val
xor_arr[key+1] = tmp
}
for key, val := range queries {
res[key] = xor_arr[val[0]] ^ xor_arr[val[1]+1]
}
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.107.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726237822.A.6CD.html