Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 树状数组实现代码

Posted by a280920481 at 2018-11-19 20:25:42 on Problem 3468
```#include <iostream>
using namespace std;

long long bit0[400005], bit1[400005];//两个 树状数组

void add0(int p, long long x);//使 bit0 的第 p 个元素加 x

long long sum0(int p);//获取 bit0 的 [1, p] 区间的和

void add1(int p, long long x);//使 bit1 的第 p 个元素加 x

long long sum1(int p);//获取 bit1 的 [1, p] 区间的和

void setvalue(int left, int right, long long x);//将 [left, right] 区间的每一个数加上 x

long long getvalue(int left, int right);//获取 [left, right] 区间的和

int pSize = 1;//元素个数

int main()
{
int N, Q, v, left, right;//数的个数 操作次数 加数 左端点 右端点
char ch;//用于接收字符

cin >> N >> Q;

while (pSize < N)
{
pSize <<= 1;
}
//此时 pSize 为元素个数

for (int i = 1; i <= N; i++)
{
cin >> v;
}
//赋初值

for (int i = 0; i < Q; i++)
{
cin >> ch;
if (ch == 'Q')
{
cin >> left >> right;

cout << getvalue(left, right) << '\n';
}
else
{
cin >> left >> right >> v;

setvalue(left, right, v);
}
}

return 0;
}

void add0(int p, long long x)
{
while (p <= pSize)
{
bit0[p] += x;
p += (p & (-p));
}
return;
}

void add1(int p, long long x)
{
while (p <= pSize)
{
bit1[p] += x;
p += (p & (-p));
}
return;
}

long long sum0(int p)
{
long long s = 0;

while (p)
{
s += bit0[p];
p -= (p & (-p));
}
return s;
}

long long sum1(int p)
{
long long s = 0;

while (p)
{
s += bit1[p];
p -= (p & (-p));
}
return s;
}

void setvalue(int left, int right, long long x)
{
add0(left, x * (1 - left));//即  -x * (left - 1)
add0(right + 1, x * right);
add1(right + 1, -x);

return;
}

long long getvalue(int left, int right)
{
left--;
return sum1(right) * right + sum0(right) - sum1(left) * left - sum0(left);
}

```

Followed by:

User ID:
Title:

Content: