Overview

This problem requires processing \(Q\) operations of range addition (operation 1) and range sum (operation 2). To handle each operation efficiently, we use a cleverly designed Fenwick Tree (BIT).

Analysis

If we naively update all elements in \(l..r\) for each operation 1, each operation takes \(O(N)\) in the worst case, resulting in \(O(NQ)\) overall, which is too slow for \(N,Q \le 10^5\).

What we need is to perform both of the following efficiently:

• Addition to a range \([l,r]\) (range add)
• Sum of a range \([l,r]\) (range sum)

A BIT is typically good at “point update and prefix sum,” but by leveraging the relationship between difference arrays and prefix sums, we can handle “range add and range sum” in \(O(\log N)\) per operation.

The key ideas are: - For “range add,” we only update the endpoints using a difference array - For “range sum,” we need to further accumulate “each element’s value,” which requires using two BITs to arrange the formula properly

Algorithm

1) Representing Range Addition with Differences

For array \(A\), define the difference array \(D\) as: - \(D[1] = A[1]\) - \(D[i] = A[i] - A[i-1] \ (i\ge2)\)

Adding \(v\) to range \([l,r]\) becomes just two point updates in the difference array: - \(D[l] += v\) - \(D[r+1] -= v\) (only when \(r+1 \le N\))

Then each element can be recovered as: - \(A[x] = \sum_{i=1}^{x} D[i]\)

If we manage this difference \(D\) with a BIT (bit1) for “point update and prefix sum,” any \(A[x]\) can be obtained as: - \(A[x] = \text{bit1.sum}(x)\)

2) Range Sum is “Prefix Sum of Prefix Sums”

To compute range sums, we need the prefix sum \(S(x)=\sum_{i=1}^{x} A[i]\).

Using the difference array: [ A[i]=\sum{j=1}^{i}D[j] ] so [ S(x)=\sum{i=1}^{x}A[i] =\sum{i=1}^{x}\sum{j=1}^{i}D[j] =\sum{j=1}^{x}D[j]\cdot(x-j+1) ] Rearranging: [ S(x)= (x+1)\sum{j=1}^{x}D[j] - \sum_{j=1}^{x}D[j]\cdot j ]

Here: - \(\sum_{j=1}^{x} D[j]\) is bit1.sum(x) - To manage \(\sum_{j=1}^{x} D[j]\cdot j\), we prepare a second BIT (bit2) that can compute the prefix sum of \(D[j]\cdot j\)

In implementation, we design the update values so that the commonly used equivalent form holds: [ S(x)= \text{bit1.sum}(x)\cdot x - \text{bit2.sum}(x) ]

3) Specific BIT Updates for Range Add

When adding \(v\) to range \([l,r]\), the differences are: - \(D[l] += v\) - \(D[r+1] -= v\)

At this time, we insert “correction values to make the formula hold” into bit2 (as shown in the code):

• bit1.add(l, v), bit1.add(r+1, -v)
• bit2.add(l, v*(l-1)), bit2.add(r+1, -v*r)

Then: - prefix_sum(x) = bit1.sum(x)*x - bit2.sum(x) gives “the sum from \(1\) to \(x\).”

Finally, the range sum is: [ \sum_{i=l}^{r}A[i] = S®-S(l-1) ]

4) Incorporating the Initial Array \(C_i\)

Initial values can also be handled uniformly by treating them as “adding \(C_i\) to range \([i,i]\)” and calling the same range_add (this approach is used in the code).

Complexity

• Time complexity: \(O((N+Q)\log N)\)
  (Initialization \(N\) times + each query \(O(\log N)\))
• Space complexity: \(O(N)\)
  (Two BITs are maintained)

Implementation Notes

• Use 1-indexed implementation (works well with BIT). Since the input is also \(1..N\), it can be used as-is.

• When updating, only reflect to \(r+1\) when \(r+1 \le N\) (to prevent out-of-bounds access).

• Since there is a lot of output, we speed things up by using sys.stdin.buffer.read(), converting to an array, and outputting everything at once at the end.

• The total values can become very large (on the order of \(10^5 \times 10^4 \times 10^5\)), but Python’s int (arbitrary precision) handles this safely.

  Source Code

import sys

class BIT:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        while i <= n:
            self.bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    bit1 = BIT(N)
    bit2 = BIT(N)

    def range_add(l, r, v):
        bit1.add(l, v)
        if r + 1 <= N:
            bit1.add(r + 1, -v)
        bit2.add(l, v * (l - 1))
        if r + 1 <= N:
            bit2.add(r + 1, -v * r)

    def prefix_sum(x):
        return bit1.sum(x) * x - bit2.sum(x)

    def range_sum(l, r):
        return prefix_sum(r) - prefix_sum(l - 1)

    # initialize with C_i
    for i in range(1, N + 1):
        c = next(it)
        if c:
            range_add(i, i, c)

    out = []
    for _ in range(Q):
        t = next(it)
        if t == 1:
            l = next(it); r = next(it); v = next(it)
            range_add(l, r, v)
        else:
            l = next(it); r = next(it)
            out.append(str(range_sum(l, r)))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.