<p>You are given two <strong>0-indexed</strong> arrays <code>nums1</code> and <code>nums2</code> and a 2D array <code>queries</code> of queries. There are three types of queries:</p>

<ol>
	<li>For a query of type 1, <code>queries[i]&nbsp;= [1, l, r]</code>. Flip the values from <code>0</code> to <code>1</code> and from <code>1</code> to <code>0</code> in <code>nums1</code>&nbsp;from index <code>l</code> to index <code>r</code>. Both <code>l</code> and <code>r</code> are <strong>0-indexed</strong>.</li>
	<li>For a query of type 2, <code>queries[i]&nbsp;= [2, p, 0]</code>. For every index <code>0 &lt;= i &lt; n</code>, set&nbsp;<code>nums2[i] =&nbsp;nums2[i]&nbsp;+ nums1[i]&nbsp;* p</code>.</li>
	<li>For a query of type 3, <code>queries[i]&nbsp;= [3, 0, 0]</code>. Find the sum of the elements in <code>nums2</code>.</li>
</ol>

<p>Return <em>an array containing all the answers to the third type&nbsp;queries.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
<strong>Output:</strong> [3]
<strong>Explanation:</strong> After the first query nums1 becomes [1,1,1]. After the second query, nums2 becomes [1,1,1], so the answer to the third query is 3. Thus, [3] is returned.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
<strong>Output:</strong> [5]
<strong>Explanation:</strong> After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums1.length,nums2.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums1.length = nums2.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code><font face="monospace">queries[i].length = 3</font></code></li>
	<li><code><font face="monospace">0 &lt;= l &lt;= r &lt;= nums1.length - 1</font></code></li>
	<li><code><font face="monospace">0 &lt;= p &lt;= 10<sup>6</sup></font></code></li>
	<li><code>0 &lt;= nums1[i] &lt;= 1</code></li>
	<li><code>0 &lt;= nums2[i] &lt;= 10<sup>9</sup></code></li>
</ul>

from math import log2, floor, ceil

def next_power_of_2(n):
    # If n is already a power of 2, return n
    if n & (n - 1) == 0:
        return n
    # Otherwise, return the next power of 2
    return 1 << n.bit_length()

def pad_data(data):
    n = len(data)
    width = next_power_of_2(n)
    data += [0] * (width - n)
    return data

class SegmentTree:
    def __init__(self, data):
        self.original_n = len(data)
        self.data = pad_data(data)
        self.n = len(data)
        self.height = ceil(log2(self.original_n)) + 1

        # print(f"Initialized with original_n: {self.original_n}, n: {self.n}, height: {self.height}")

        # Initialize segment tree array with 4 * n space
        self.t = [0] * (2 ** (self.height + 1))
        # Initialize lazily applied flips
        self.lazy = [0] * (2 ** (self.height + 1))

        self.build(data, 1, 0, self.n - 1)

        self.print_state()

    def push(self, v):
        if not self.lazy[v]: return # Nothing to flip

        # print(f"Pushing v: {v} down to children")

        self.lazy[v * 2] ^= self.lazy[v]
        self.lazy[v * 2 + 1] ^= self.lazy[v]
        self.lazy[v] = 0

        # If the flip Flipping a sum is 2^H - t[v]
        # H = # of levels of children below
        next_level = floor(log2(v*2))
        range = 2 ** (self.height - next_level - 1)
        self.t[v * 2] = range - self.t[v * 2]
        self.t[v * 2 + 1] = range - self.t[v * 2 + 1]

        return

    def flip_sum(self, v):
        # The "flip" of a sum node is 2^H - t[v]
        level = floor(log2(v))
        range = 2 ** (self.height - level - 1)
        self.t[v] = range - self.t[v]

    def build(self, a, v, tl, tr):
        if tl == tr:
            # Leaf node, assign the corresponding value from the array
            self.t[v] = a[tl]
        else:
            tm = (tl + tr) // 2
            # Build left and right child recursively
            self.build(a, v * 2, tl, tm)
            self.build(a, v * 2 + 1, tm + 1, tr)
            # Lazy node will store # of flips to apply
            self.lazy[v] = 0
            # Internal node will store sum of children
            self.t[v] = self.t[v * 2] + self.t[v * 2 + 1]

    def flip(self, l, r):
        self.print_state()
        self.flip_segment(1, 1, self.n, l, r)
        self.print_state()

    def flip_segment(self, v, tl, tr, l, r):
        if (l > r):
            return

        # print("Flipping v: ", v, "tl: ", tl, "tr: ", tr, "l: ", l, "r: ", r)

        if (l == tl and tr == r):
            # Mark entire range to lazily flip
            # print("marking flip", v)
            self.lazy[v] ^= 1
            self.flip_sum(v)
        else:
            self.push(v)  # propagate lazy flip before we recurse
            tm = (tl + tr) // 2
            self.flip_segment(v * 2, tl, tm, l, min(r, tm)) # left
            self.flip_segment(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r) # right
            self.t[v] = self.t[v * 2] + self.t[v * 2 + 1] # update sum

    def print_state(self):
        # print(f"Segment tree: {self.t}")
        # print(f"Lazy tree:    {self.lazy}")
        return

    def get_sum(self):
        self.print_state()
        result = self.query(1, 1, self.n, 1, self.original_n)
        self.print_state()
        return result

    def query(self, v, tl, tr, l, r):
        if l > r: return 0

        # print(f"Querying v: {v}, tl: {tl}, tr: {tr}, l: {l}, r: {r}")
        if l == tl and r == tr:
            # print(f"Found sum: {self.t[v]}")
            return self.t[v]
        tm = (tl + tr) // 2

        # Propagate the flip(s) to the children & reset current node
        self.push(v)

        return self.query(v * 2, tl, tm, l, min(r, tm)) \
             + self.query(v * 2 + 1, tm + 1, tr, max(l, tm+1), r)


class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        st = SegmentTree(nums1)
        sums = sum(nums2)
        results = []
        n = len(nums1)

        for qtype, arg1, arg2 in queries:
            match qtype:
                case 1: # flip segment between arg1 and arg2
                    st.flip(arg1 + 1, arg2 + 1)
                    continue
                case 2: # add arg1 * sum(nums1) to sums
                    sums += arg1 * st.get_sum()
                    continue
                case 3: # report
                    results.append(sums)
                    continue
        
        return results

48200