oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

fenwicktree Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

fenwick.html

Problem Description

Rar the Cat has an array of N integers. Initially, the ith integer has the value Ai.

Rar the Cat wants you to answer queries and updates, there will be a total of M queries and updates, in order.

For each query, Rar the Cat will provide you with two integers x and y where 0 ≤ x ≤ y < N. You are to respond with the sum of the integers from A[x] to A[y] inclusive.

For each update, Rar the Cat will provide you with three integers, a, b and c. This means you have to add c to every integer from A[a] to A[b].

Limits

For all testcases, -(103) ≤ Ai, c ≤ 103, 0 ≤ x ≤ y < N, 0 ≤ a ≤ b < N.

Subtask 1 (57%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000. For all update commands, a = b.

Subtask 2 (43%): 1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000. No further restrictions.

Subtask 3 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the array A.

The next line will contain a single integer, M.

M lines will follow. The first character of each line will be T.

If T is 0, then it represents a query. 2 integers will then follow, x and y.

If T is 1, then it represents a update. 3 integers will then follow, a, b followed by c.

Output

For each line of query, you are to output the sum of A[x] to A[y] inclusive, on a single line.

Sample Testcase 1

Input

10
1 2 9 5 7 6 3 4 2 2
5
0 0 1
0 0 9
1 1 8 7
0 0 9
0 5 7

Output

3
41
97
34

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
157201s64MBMinimum
243411s64MBMinimum
3011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o fenwicktree -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.