Let's first forget about given array, imagine it's filled with zeroes. Now, you only need to find out how much was added to i-th position.

Let's do a following trick: store not how much was added to the i-th position, but how much was added to all positions, divisable by i. Let's store it in some array called add[i]. Now notice that add[l..r] += x is exactly the second type of queries we need to process.

The only thing we have to figure out is how to answer the first type of queries. It's quite simple. Let vector divisors[i] be all divisors of number i. Now, to find answer, you just have to do answer += add[x], for all x in divisors[i], and then asnwer += a[i], where a[i] is value of i-th position in initial array. You can estimate amount of divisors of i like i^(1/3) * 2 (it's a well known fact).

Complexity of this solution will be O(n^(1/3)) for first query and O(sqrt(n)) for second if you use sqrt-decomposition, and O(n^(1/3) * log n) for first query and O(log n) for second if you use segment tree/fenwick tree.

Here's my solution: http://pastebin.com/MNfqHFD0

You can actually get to sqrt(N) for update and cuberoot(N) for query if you use sqrt decomposition for processing range updates. http://ideone.com/W3LNJJ

• Let A_i be the initial value of element i.
• With a sieve-like loop, make a list of all divisors for numbers  ≤ 300000. Let D_x be the list of divisors for number x.
• Let U_i be the total updates performed to element i. Notice that adding d to all U_i in a range [l, r] is the same as adding d to U_l and subtracting d from U_r + 1, and then working with prefix sums. This can be done efficiently in O(_logN) with a BIT.
• Now, the answer to queries of the second type for a certain element i is , which works in .

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int A[300005], N, Q;
ll T[300005];
vector<int> Divs[300005];

ll query_bit(int x)
{
    ll ret = 0;
    while(x)
    {
        ret += T[x];
        x -= x&-x;
    }
    return ret;
}

void update(int x, int v)
{
    while(x <= 300001)
    {
        T[x] += v;
        x += x&-x;
    }
}

ll query(int n)
{
    ll ret = A[n];
    for(int d : Divs[n]) ret += query_bit(d);
    return ret;
}

int main()
{
    for(int i = 1; i <= 300000; i++) for(int j = i; j <= 300000; j += i) Divs[j].push_back(i);

    cin >> N;
    for(int i = 1; i <= N; i++) scanf("%d", &A[i]);

    cin >> Q;

    while(Q--)
    {
        int t;
        scanf("%d", &t);
        if(t == 1)
        {
            int i;
            scanf("%d", &i);
            cout << query(i) << "\n";
        }
        else
        {
            int l,r,d;
            scanf("%d %d %d", &l, &r, &d);
            update(l,d);
            update(r+1,-d);
        }
    }
}