트리/세그먼트 트리

XOR (Top-down)

4gats 2024. 3. 14. 14:10

https://www.acmicpc.net/problem/12844

 

12844번: XOR

크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다.

www.acmicpc.net

XOR이란?

1 0

0 1

만 1이고 나머지는 0

 

XOR은 교환 법칙이 성립한다.

 

스위치 문제와 유사한듯 다르다.

스위치 문제에서는 lazy 배열의 값을 확인했다.

 

  • 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다.

만약 구간 업데이트의 크기가 짝수라면

k가 짝수번 XOR 되면 0이 되어

값이 그대로 유지된다.

 

즉, end - start + 1이 짝수인지, 홀수인지를 체크해야한다.

홀수이면 tree[node] ^ lazy[node];

 

구간 합에서는

update_range()를 하면

변경 범위 안에 있으면

tree[node += (end - start + 1) * diff;

를 했었다.

 

XOR에서는

lazy[node] ^= k;

를 하고

update_lazy() 함수로 간다.

 

<소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
vector<int> arr;
vector<int> lazy;
vector<int> tree;
 
int make_tree(int node, int start, int end)
{
    if (start == end)
    {
        return tree[node] = arr[start];
    }
 
    int mid = start + (end - start) / 2;
 
    int left_val = make_tree(node * 2, start, mid);
    int right_val = make_tree(node * 2 + 1, mid + 1, end);
    tree[node] = left_val ^ right_val;
    return tree[node];
}
 
void update_lazy(int node, int start, int end)
{
    if (lazy[node] != 0)
    {
        // 범위가 홀수인가 짝수인가
        if ((end - start + 1) % 2 == 1)
        {
            tree[node] ^= lazy[node];
        }
 
        // lazy propagation
        if (start != end)
        {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
        lazy[node] = 0; 
    }
}
 
void update_range(int node, int start, int end, int left, int right, int k)
{
    update_lazy(node, start, end);
 
    if (left > end || right < start)
        return;
 
    if (start >= left && end <= right)
    {
        lazy[node] ^= k;
        // 홀수인지 짝수인지 체크
        update_lazy(node, start, end);
        return;
    }
 
    int mid = start + (end - start) / 2;
    update_range(node * 2, start, mid, left, right, k);
    update_range(node * 2 + 1, mid + 1, end, left, right, k);
    tree[node] = tree[node * 2] ^ tree[node * 2 + 1];
}
 
 
int query(int node, int start, int end, int left, int right)
{
    update_lazy(node, start, end);
 
    if (left > end || right < start)
        return 0;
 
    if (start >= left && end <= right)
        return tree[node];
 
    int mid = start + (end - start) / 2;
    int left_val = query(node * 2, start, mid, left, right);
    int right_val = query(node * 2 + 1, mid + 1, end, left, right);
    return left_val ^ right_val;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
 
    arr.resize(n + 1);
    int height = (int)ceil(log2(n));
    int tree_size = (1 << (height + 1));
    tree.resize(tree_size);
    lazy.resize(tree_size);
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    make_tree(1, 0, n - 1);
    
    int m;
    cin >> m;
 
 
    while (m--)
    {
        int q;
        cin >> q;
        if (q == 1)
        {
            int i, j, diff;
            cin >> i >> j >> diff;
            update_range(1, 0, n - 1, i, j, diff);
        }
        else if (q == 2)
        {
            int a, b;
            cin >> a >> b;
            cout << query(1, 0, n - 1, a, b) << '\n';
        }
    }
 
}
 cs