Fenwick 树状数组

原理

1. 简单题

洛谷 P3374 【模板】树状数组 1

洛谷 P3368 【模板】树状数组 2

洛谷 P5057 [CQOI2006] 简单题

洛谷 P2068 统计和

洛谷 P4939 Agent2

洛谷 P2880 [USACO07JAN] Balanced Lineup G

洛谷 P6225 [eJOI 2019] 异或橙子

洛谷 P1908 逆序对

洛谷 P1774 最接近神的人

洛谷 P4378 [USACO18OPEN] Out of Sorts S

2.中等题

洛谷 P2357 守墓人

原理

luogu P3374 【模板】树状数组 1

题面描述：

已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 x；
• 求出某区间每一个数的和。

代码

#include <iostream>
using namespace std;
#define int long long
#define lowbit(x) ((x)&-(x))

const int N = 1e6 + 10;

int n,m;
int tree[N];

void update(int x,int d) {
	while(x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

void del(int x,int d) {
	while(x > 0) {
		tree[x] -= d;
		x -= lowbit(x);
	}
}

int fin(int x) {
	int re = 0;
	while(x) {
		re += tree[x];
		x -= lowbit(x);
	}
	return re;
}

signed main() {
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++) {
		int num;
		cin >> num;
		update(i,num);
	}
	for(int i = 0 ; i < m ; i ++) {
		int op;
		cin >> op;
		if(op == 1) {
			int x,d;
			cin >> x >> d;
			update(x,d);
		} else {
			int st,en;
			cin >> st >> en;
			cout << fin(en) - fin(st-1)<< "\n";
		}
	}
	return 0;
}

luogu P3368 【模板】树状数组 2

题面描述：

已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 x；
2. 求出某一个数的值。

解题思路：

其实这道题和前面那道模板题本质上是一样的，只需要对数列初始的时候进行前缀和，然后就能利用差分操作进行快速的区间加法操作和单点查询操作了

这也是很经典的利用树状数组优化前缀和差分的操作了。

代码：

#include <iostream>
using namespace std;
#define int long long
#define lowbit(x) ((x)&-(x)) 

const int N = 1e6 + 10;

int n,m,old = 0;
int tree[N];

void update(int x,int d) {
	while(x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

void del(int x,int d) {
	while(x > 0) {
		tree[x] -= d;
		x -= lowbit(x);
	}
}

int fin(int x) {
	int re = 0;
	while(x) {
		re += tree[x];
		x -= lowbit(x);
	}
	return re;
}

signed main() {
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++) {
		int num;
		cin >> num;
		update(i,num-old);
		old = num;
	}
	for(int i = 0 ; i < m ; i ++) {
		int op;
		cin >> op;
		if(op == 1) {
			int x,y,d;
			cin >> x >> y >> d;
			update(x,d);
			update(y+1,d*(-1));;
		} else {
			int x;
			cin >> x;
			cout << fin(x)<< "\n";
		}
	}
	return 0;
}

luogu P5057 [CQOI2006] 简单题

题面描述：

有一个 n 个元素的数组，每个元素初始均为 0。有 m 条指令，每条指令为两种操作中的一种：

1. 让其中一段连续序列数字反转；（即 0 变 1，1 变 0）
2. 询问某个元素的值。

解题思路：

实际上仍然是前缀和的思路，我们可以注意到，翻转奇数次就是 1 ，翻转偶数次就是 0 ， 所以我们只要用前缀和维护某个数反转了几次即可。

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }

    int select(const T &k) {
        int x = 0;
        T cur{}; 
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n,m;
    std::cin >> n >> m;
    Fenwick<int> f(n+2);
    while(m--) {
        int op;
        std::cin >> op;
        if(op == 1) {
            int l,r;
            std::cin >> l >> r;
            f.add(l,1);
            f.add(r+1,-1);
        } else {
            int i;
            std::cin >> i;
            std::cout << ((f.sum(i) & 1) == 0 ? 0 : 1) << "\n";
        }
    }
    return 0;
}

luogu P2068 统计和

题面描述：

给定一个长度为 n(0 ≤ n ≤ 10⁵)，初始值都为 0 的序列，x(0 ≤ x ≤ 10⁵) 次的修改某些位置上的数字，每次加上一个数，并在此期间提出 y(0 ≤ y ≤ 10⁵) 个问题，求每段区间的和。

解题思路：

这题实际上就是经典的 单点修改 + 区间查询 ， 区间查询可以从前缀和演变过来，两个一前一后的前缀和相减之后，得到的就是区间和了

代码：

#include <iostream>
using namespace std;
#define int long long 
#define lowbit(x) ((x)&-(x))

const int N = 1e6 + 10;

int n,w;
int tree[N];

void update(int x,int d) {
	while(x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

int fin(int x) {
	int re = 0;
	while(x) {
		re += tree[x];
		x -= lowbit(x);
	}
	return re;
}

signed main() {
	cin >> n >> w;
	while(w--) {
		char op;
		cin >> op;
		if(op == 'x') {
			int x,d;
			cin >> x >> d;
			update(x,d);
		} else {
			int x,y;
			cin >> x >> y;
			cout << fin(y) - fin(x-1) << "\n";
		}
	}
	return 0;
}

luogu P4939 Agent2

题面描述：

在一个时间长度为 N 天的行动中，指挥对你下达了 M 条命令操作，命令操作如下：

1. 输入 0, a, b，这代表在第 a 天到第 b 天，有一名 队员要行动。
2. 输入 1 a，这代表 指挥询问你根据目前的信息，在第 a 天有多少名队员要行动。

解题思路：

实际上就是对差分数组进行 单点修改 和 用前缀和操作进行查询 的经典操作

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
#define lowbit(x) (x&-x)


template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }

    int select(const T &k) {
        int x = 0;
        T cur{}; 
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    
    int n,m;
    std::cin >> n >> m;
    Fenwick<int> f(n+2);

    while(m--) {
        int op;
        std::cin >> op;
        if(op == 0) {
            int a,b;
            std::cin >> a >> b;
            f.add(a,1);
            f.add(b+1,-1);
        } else {
            int a;
            std::cin >> a;
            std::cout << f.sum(a) << "\n";
        }
    }
    
    return 0;
}

luogu P2880 [USACO07JAN] Balanced Lineup G

题面描述：

给你一个长度为 n 的序列，询问 q 次，每次询问给你 a、b ，要求你给出序列区间 a、b 中的极差

解题思路：

实际上我们需要使用树状数组来维护区间最大值和区间最小值。

更新操作原理：

• 首先将当前位置x的值设为d
• 然后更新当前节点的兄弟节点信息（在同一个父节点下的其他节点）
• 最后通过不断加上lowbit(x)更新所有包含该节点的父节点

查询操作原理：

• 从右往左遍历区间 [y, x]
• 对于无法被树状数组覆盖的部分，直接比较原始数组的值
• 对于能够被树状数组覆盖的区间，利用树状数组查询该区间的最大值

PS: 感觉区间最值维护的题目，不修改的不如上 ST表，带修改的不如上线段树，树状数组有点神秘了

#include <iostream>
#include <map>
#define lowbit(x) ((x)&-(x))
#define int long long

const int N = 1e6;
int n,q;
int treeX[N],treeN[N],num[N];

void UpdateMax(int x , int d) {
	treeX[x] = d;
	for(int i = 1 ; i < lowbit(x) ; i <<= 1) {
		treeX[x] = std::max(treeX[x] , treeX[x-i]);
	}
	while(x <= n) {
		treeX[x] = std::max(treeX[x] , d);
		x += lowbit(x);
	}
}

void UpdateMin(int x , int d)
{
	treeN[x] = d;
	for(int i = 1 ; i < lowbit(x) ; i <<= 1)
	{
		treeN[x] = std::min(treeN[x] , treeN[x-i]);
	}
	while(x <= n)
	{
		treeN[x] = std::min(treeN[x] , d);
		x += lowbit(x);
	}
}

int FindMax(int x,int y)
{
	int re = 0;
	while(x >= y)
	{
		re = std::max(re , num[x]);
		x--;
		while(x - y > lowbit(x))
		{
			re = std::max(re , treeX[x]);
			x -= lowbit(x);
		}
	}
	return re;
}

int FindMin(int x,int y)
{
	if(x == y) return 0;
	int re = 1e16;
	while(x >= y)
	{
		re = std::min(re , num[x]);
		x--;
		while(x - y > lowbit(x))
		{
			re = std::min(re , treeN[x]);
			x -= lowbit(x);
		}
	}
	return re;
}

signed main()
{
	std::cin >> n >> q;
	for(int i = 1 ; i <= n;i ++)
	{
		std::cin >> num[i];
		UpdateMax(i , num[i]);
		UpdateMin(i , num[i]);
	}
		
	for(int i = 0 ; i < q ; i ++)
	{
		int a,b;
		std::cin >> a >> b;
		if(a!=b)
			std::cout << FindMax(b,a) - FindMin(b,a) << "\n";
		else
			std::cout << 0 << "\n";
	}
	return 0;
}

luogu P6225 [eJOI 2019] 异或橙子

题面描述：

给你一个长度为 n 的序列，你会进行 q 次操作：

操作1：将序列第 i 个数修改为 x

操作2：求序列的区间 l、r 中所有区间的异或和的异或和，例如 l = 2, r = 4 的情况，记橙子序列 A 中第 i 个橙子的整数是 a_i，那么他要求的就是： a₂ ⊕ a₃ ⊕ a₄ ⊕ (a₂ ⊕ a₃) ⊕ (a₃ ⊕ a₄) ⊕ (a₂ ⊕ a₃ ⊕ a₄)

解题思路：

首先我们知道异或的性质，一个数 a 自己与自己异或奇数次，结果是自己本身；自己与自己异或偶数次，结果为 0.

修改操作很好维护，我们要处理的关键点应该是区间内所有区间的异或和的异或和

那么我们就应该要计算出这个区间内的某一个数和自己异或了多少次

这句话我们可以翻译为：这个区间内有多少个连续的区间包括了他本身

假设要求区间为 l、r ，这个数下标为 i ，那么这个数就异或了 (i − l + 1) * (r − i + 1) 次

事实上，我们不需要处理这个数异或和为 0 的情况，也就是，我们只需要处理 (i − l + 1) * (r − i + 1) 为奇数时的情况。

两个数相乘为奇数的时候，只有奇数乘奇数一种情况，所以只有在 i 和 l 奇偶性相同且 i 和 r 奇偶性相同的时候，才需要计算

也就是说：

• 如果 l 和 r 奇偶性不同，所有数都异或了偶数次，我们可以直接输出 0 ；
• 如果 l 和 r 奇偶性相同，我们只需要计算下标在 l 和 r 之间且下标奇偶性与他们相同的元素的异或和即可。

从中我们可以看出，我们可以分奇偶性去讨论这个结果，因此分奇偶性两个树状数组去维护区间异或和会比较方便。

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)

using vi = std::vector<int>;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i] ^= v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans ^= a[i];
        }
        return ans;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n,m;
    std::cin >> n >> m;
    Fenwick<int> f_odd(n+10),f_even(n+10);
    vi a(n+10);

    for(int i = 1; i <= n; i ++) {
        int x;
        std::cin >> x;
        if(i & 1) {
            f_odd.add(i,x);
        } else {
            f_even.add(i,x);
        }
        a[i] = x;
    }

    while(m--) {
        int op;
        std::cin >> op;
        if(op == 1) {
            int i,j;
            std::cin >> i >> j;
            if(i & 1) {
                f_odd.add(i,j ^ a[i]);
            } else {
                f_even.add(i,j ^ a[i]);
            }
            a[i] = j;
        } else {
            int l,r;
            std::cin >> l >> r;
            if((r - l) & 1) {
                std::cout << 0 << "\n";
                continue;
            }
            if(l & 1) {
                std::cout << (f_odd.sum(r) ^ f_odd.sum(l-1)) << '\n';
            } else {
                std::cout << (f_even.sum(r) ^ f_even.sum(l-1)) << '\n';
            }
        }
    }
    return 0;
}

luogu P1908 逆序对

题面描述：

给你一个长度为 n 的序列 a ，要求你给出 i < j 且 a_i > a_j 的无序数对 {i, j} 的个数（序列中的数 a_i 不超过 10⁹ ，1 ≤ n ≤ 5 × 10⁵）

解题思路

首先，10⁹ 太大了，我们无法开这么大的数组，但是 n 的个数不是很大，我们存的下 n 个数，并且我们又只需要这 n 个数之间的大小关系，所以我们可以先对这 n 个数进行离散化。

然后我们就要计算逆序对了。

如何利用树状数组计算逆序对呢？

我们可以对利用树状数组对这个序列反过来计数，每次 add 一个数之后，我们统计比这个数小的数的个数，即可知道这个数作为 a_i 的逆序对的个数了

PS： 虽然归并排序同样可以计算逆序对个数，但是我个人认为还是树状数组比较好写

代码：

#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&-(x))
#define int long long

const int N = 1e6 + 10;

int n,num,tree[N],rank[N];
struct point{
	int num,val;
}a[N];

bool cmp(point a,point b) {
	if(a.val == b.val) return a.num < b.num;
	return a.val < b.val;
}

void update(int x,int d) {
	while(x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

int sum(int x) {
	int re = 0;
	while(x) {
		re += tree[x];
		x -= lowbit(x);
	}
	return re;
}

signed main() {
	std::cin >> n;
	for(int i = 1 ; i <= n ; i ++) {
		std::cin >> a[i].val;
		a[i].num = i;
	}
	
	std::sort(a+1,a+n+1,cmp);
	for(int i = 1 ; i <= n ; i ++) rank[a[i].num] = i;
	int ans = 0;
	
	for(int i = 1 ; i <= n ; i ++) {
		update(rank[i],1);
		ans += i - sum(rank[i]);
	}
	
	std::cout << ans;
}

luogu P1774 最接近神的人

题面描述：

给你一个长度为 n 的序列，你可以选择任意两个位置不同数字进行交换，问你至少需要交换多少次才能使整个序列变成非下降序列。

1 ≤ n ≤ 5 × 10⁵， A_i ∈ [ − 2³¹, 2³¹)

解题思路：

经验丰富的同学一眼就能看得出来这道题本质上要求的就是逆序对数，因为每两个逆序对数他们的大小位置都需要逆转，所以可以看成他们都需要交换一次

#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&-(x))
#define int long long

const int N = 1e6 + 10;

int n,num,tree[N],rank[N];
struct point{
	int num,val;
}a[N];

bool cmp(point a,point b) {
	if(a.val == b.val) return a.num < b.num;
	return a.val < b.val;
}

void update(int x,int d) {
	while(x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

int sum(int x) {
	int re = 0;
	while(x) {
		re += tree[x];
		x -= lowbit(x);
	}
	return re;
}

signed main() {
	std::cin >> n;
	for(int i = 1 ; i <= n ; i ++) {
		std::cin >> a[i].val;
		a[i].num = i;
	}
	
	std::sort(a+1,a+n+1,cmp);
	for(int i = 1 ; i <= n ; i ++) rank[a[i].num] = i;
	int ans = 0;
	
	for(int i = 1 ; i <= n ; i ++) {
		update(rank[i],1);
		ans += i - sum(rank[i]);
	}
	
	std::cout << ans;
}

luogu P4378 [USACO18OPEN] Out of Sorts S

题面描述：

给你一个长度为 n 的序列，以下是一段冒泡排序的伪代码：

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

其中 moo 代表输出一行moo

问：对于这个序列，执行完以上的冒泡排序后，一共输出了多少行moo

解题思路 by hs_black：

首先我们要看懂题面中的伪代码讲的是什么意思：其实就是每次输出一行的moo，然后跑一次冒泡排序，直到整个序列已经完全有序

所以，我们要输出的行数，就是他跑的冒泡排序的次数  + 1 。

那么他到底要跑多少趟冒泡排序呢？

对于一个序列, 我们称之为有序的, 当且仅当对于任意一个位置前面没有比它大的数(可以模拟一下)

对于冒泡排序有一个小性质: 每一次都会把序列未排好序的最大数“沉底”, 即推到序列尾部

比如:6 1 2 3 4 5 进行一次为 1 2 3 4 5 6

那么对于位置i, 冒泡排序进行到 i − 1 时, a_i − 1 为前 i − 1 个数中最大的一个, 如果它大于 a_i 那么它就会到 a_i 的后面

由此可推知, 每一次位置i前都会将一个比 a_i 大的数推至其后, 直至没有比它大的

那么我们对每位置求一下它前面有几个比它大就好啦(注意要将答案加一)

具体来说先进行离散化, 再树状数组求解即可

PS：也有不需要树状数组的做法，同学们可以自己探索一下

代码：

#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&-(x))
#define int long long

const int N = 1e6 + 10;

int n,num,tree[N],rank[N];
struct point{
	int num,val;
}a[N];

bool cmp(point a,point b) {
	if(a.val == b.val) return a.num < b.num;
	return a.val < b.val;
}

void update(int x,int d) {
	while(x <= n) {
		tree[x] += d;
		x += lowbit(x);
	}
}

int sum(int x) {
	int re = 0;
	while(x) {
		re += tree[x];
		x -= lowbit(x);
	}
	return re;
}

signed main() {
	std::cin >> n;
	for(int i = 1 ; i <= n ; i ++) {
		std::cin >> a[i].val;
		a[i].num = i;
	}
	
	std::sort(a+1,a+n+1,cmp);
	for(int i = 1 ; i <= n ; i ++) rank[a[i].num] = i;
	int ans = 0;
	
	for(int i = 1 ; i <= n ; i ++) {
		update(rank[i],1);
		ans = std::max(ans, i - sum(rank[i]) + 1);
	}
	
	std::cout << ans;
}

luogu P2357 守墓人

题面描述：

守墓人有 n 个墓碑，你会得到所有墓碑的初始风水值，他会进行 f 次下列操作中的一种操作：

• 操作 1 ：将 [l, r] 区间的墓碑全部增加 k
• 操作 2 ：将 1 号墓碑风水值增加 k
• 操作 3 ：将 1 号墓碑风水值降低 k
• 操作 4 ：统计区间 [l, r] 之间所有墓碑的风水值之和
• 操作 5 ：求 1 号墓碑的风水值

1 ≤ n, f ≤ 2 × 10⁵，答案不超过 64 位整数。

解题思路

从题目的数据范围，我们可以发现，我们每次操作的时间复杂度大约只能在 O(logn) 之内，

从要求来看：区间增加操作，我们需要对对原数组进行差分操作；区间求和操作，我们需要对原数组进行前缀和操作

因此，很明显这并不是一个树状数组就可以解决的问题。

三个数组：差分数组，原数组，前缀和数组；我们可以通过差分数组与原数组之间的关系 以及 原数组与前缀和数组之间的关系 ，计算一下差分数组与前缀和数组之间的关系

具体推理如下（by 胡小兔）：

位置p的前缀和 =

$$ \sum_{i=1}^{p} a[i] = \sum_{i=1}^{p}\sum_{j=1}^{i} d[j] $$

在等式最右侧的式子$\sum_{i=1}^{p}\sum_{j=1}^{i} d[j]$中，d[1] 被用了p次，d[2]被用了p − 1次……那么我们可以写出： 位置p的前缀和 =

$$ \sum_{i=1}^{p}\sum_{j=1}^{i} d[j] = \sum_{i=1}^{p} d[i]*(p-i+1) = (p+1)*\sum_{i=1}^{p} d[i] - \sum_{i=1}^{p} d[i]*i $$

那么我们可以维护两个数组的前缀和： 一个数组是 sum1[i] = d[i]， 另一个数组是 sum2[i] = d[i] * i。

代码：

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i] = a[i] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i];
        }
        return ans;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n,m;
    std::cin >> n >> m;

    int mem = 0;

    Fenwick<int> f1(n+2),f2(n+2);
    for(int i = 1 ; i <= n ; i ++) {
        int x;
        std::cin >> x;
        f1.add(i, x - mem);
        f2.add(i, (x - mem) * i);
        mem = x;
    }
    while(m--) {
        int op;
        std::cin >> op;
        if(op == 1) {
            int l,r,v;
            std::cin >> l >> r >> v;
            f1.add(l, v);
            f2.add(l, v * l);
            f1.add(r+1, - v);
            f2.add(r+1, - v * (r + 1));
        } else if(op == 2) {
            int v;
            std::cin >> v;
            f1.add(1, v);
            f1.add(2, -v);
            f2.add(1, v);
            f2.add(2, -v * 2);
        } else if(op == 3) {
            int v;
            std::cin >> v;
            f1.add(1, -v);
            f1.add(2, v);
            f2.add(1, -v);
            f2.add(2, v * 2);
        } else if(op == 4) {
            int l,r;
            std::cin >> l >> r;
            std::cout << (r + 1) * f1.sum(r) - f2.sum(r) - ((l) * f1.sum(l-1) - f2.sum(l-1)) << '\n';
        } else {
            std::cout << f1.sum(1) << '\n';
        }
    }
    return 0;
}