# d799. 区间求和

unknown
c_cpp
2 years ago
3.5 kB
112
Indexable
Never
```#include <iostream>
#include <vector>
#include <utility>
using namespace std;
void build(int L, int R, int v, vector<pair<long long int, long long int>> &node, vector<long long int> &num)
{
if (L == R)
node[v] = make_pair(num[L], 0);
else
{
int mid = (L + R) / 2;
build(L, mid, v * 2 + 1, node, num);
build(mid + 1, R, v * 2 + 2, node, num);
node[v] = make_pair(node[v * 2 + 1].first + node[v * 2 + 2].first, 0);
}
}
void update(long long int target_L, long long int target_R, long long int k, long long int v, long long int current_L, long long int current_R, vector<pair<long long int, long long int>> &node)
{
if (target_L == current_L && target_R == current_R)
node[v] = make_pair(node[v].first + (current_R - current_L + 1) * k, node[v].second + k);
else
{
long long int mid = (current_L + current_R) / 2;
if (target_R <= mid)
update(target_L, target_R, k, v * 2 + 1, current_L, mid, node);
if (mid + 1 <= target_L)
update(target_L, target_R, k, v * 2 + 2, mid + 1, current_R, node);
if (target_L <= mid && mid + 1 <= target_R)
{
update(target_L, mid, k, v * 2 + 1, current_L, mid, node);
update(mid + 1, target_R, k, v * 2 + 2, mid + 1, current_R, node);
}
node[v] = make_pair(node[v].first + (target_R - target_L + 1) * k, node[v].second);
}
}
unsigned long long int sum = 0;
void query(long long int target_L, long long int target_R, long long int lazytag, long long int v, long long int current_L, long long int current_R, vector<pair<long long int, long long int>> &node)
{
node[v] = make_pair(node[v].first + (current_R - current_L + 1) * lazytag, node[v].second + lazytag);
if (target_L == current_L && target_R == current_R)
sum += node[v].first;
else
{
long long int mid = (current_L + current_R) / 2;
if (target_R <= mid)
query(target_L, target_R, node[v].second, v * 2 + 1, current_L, mid, node);
if (mid + 1 <= target_L)
query(target_L, target_R, node[v].second, v * 2 + 2, mid + 1, current_R, node);
if (target_L <= mid && mid + 1 <= target_R)
{
query(target_L, mid, node[v].second, v * 2 + 1, current_L, mid, node);
query(mid + 1, target_R, node[v].second, v * 2 + 2, mid + 1, current_R, node);
}
node[v] = make_pair(node[v].first, 0);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<long long int> num;
num.reserve(N);
num.resize(N);
for (int i = 0; i < N; i++)
cin >> num[i];
vector<pair<long long int, long long int>> node;
node.reserve(4 * N);
node.resize(4 * N);
build(0, N - 1, 0, node, num);
int Q;
cin >> Q;
for (int c = 0; c < Q; c++)
{
int v;
cin >> v;
if (v == 1)
{
long long int target_L, target_R, k;
cin >> target_L >> target_R >> k;
update(target_L - 1, target_R - 1, k, 0, 0, N - 1, node);
}
if (v == 2)
{
long long int target_L, target_R;
cin >> target_L >> target_R;
sum = 0;
query(target_L - 1, target_R - 1, 0, 0, 0, N - 1, node);
cout << sum << '\n';
}
}
}```