CSP知识点

zifuneko · 2025-10-01 15:02:16 · 个人记录

对J组知识点进行复习并将板子放入到本文中，每复习一个知识点，将会写一篇专栏。

\text{S Goal:}\ 200 \to 100

\text{NOIP Goal: }\ 140

注意事项与调试工作

暴力

对我来说，在NOIP的任何一道题都先打暴力，暴力就是用低级的数据结构来完成部分的题目要求。然后可以尝试打正解或极大分数，正确性可以使用对拍进行验证。

对拍

下面是文件名称所代表的意义：	文件名	意义
gen.cpp	生成随机样例
code.cpp	解答题目正解或部分分的代码
bl.cpp	暴力（一定要正确）
diff.cpp	比较函数

我们以 a+b problem 作为例子举例，环境为 Noi Ubuntu：

gen.cpp（生成随机值）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    mt19937 rnd(time(0)); // 随机种子

    cout << rnd() % 100000+1 << ' ' << rnd() % 100000+1 << endl;
    return 0;
}

code.cpp（有 \frac{1}{20} 的概率出错）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if((a + b) % 20 == 0) cout << a + b + 1 << endl;
    else cout << a + b << endl;
    return 0;
}

bl.cpp（暴力）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

diff.cpp

未带后缀名的如 gen、code、bl 为编译后的文件。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    for(int i=1; ; i++)
    {
        cout << "No. " << i << endl;
        // 把数据生成器生成的数据写入 qwq.in(输入数据)
        system("./gen > qwq.in");
        // 把 qwq.in 的内容交给 code(正解) 运行，输出到 code.out
        system("./code < qwq.in > code.out");
        // 把 qwq.in 的内容交给 bl(暴力) 运行，输出到 code.ans
        system("./bl < qwq.in > code.ans");
        // 比较 code.out 与 code.ans，若不同则获得了一组错误样例
        if(system("diff code.out code.ans") != 0)
            {cout << "GG" << endl; break;}
    }
}

调试与检查

求代码中两地的时间差

auto t1 = clock();
int a = 0; for(int i=0; i<1e5; i++) rand();
auto t2 = clock();
cerr << t2-t1 << " ms" << endl;

防止 TLE

void dfs()
{
    if(sum > ans) return;
    if(clock() - t1 > 950) {cout << ans; exit(0);}
}

cout << "Running at Line" << __LINE__ << "\n";

检查 RE

ASAN & UBSAN （仅在Linux）
```
-fsanitize=address -fsanitize=undefined
```

gdb

g++ a.cpp -o a -std=c++14 -g
gdb a
// Used "r"; Quit "q".

STL 调试模式

-D_GLIBCXX_DEBUG

防止数值溢出

-ftrapv

注意事项

今年报名情况分析——机位上升、小学生不让考，对应获奖不会变难。
考试前的准备
- 注意休息，特别是前一晚。
- 赛前饮食要注意，别太撑。
- 比赛需要的物资准备好。
考试的一些经验：
- 审题：
- 如果不会被干扰：建议先把题目都看一遍，否则可以多看一题。
- 一定要看清楚题面，看看是否有偷藏信息。
- 样例一定要走一遍、样例解释一定要看懂。（防止读错题）
- 数据范围要看清。
- 解题：
- 题目再翻译很重要（自然描述——>数学描述）。
- 标注重要信息，防止忘记。
- 梳理思维链路，列出关键问题，不要想一出是一出。
- 先有解法后有代码，不要混在一起。
- 从简单开始（弱数据范围、弱约束条件）。
- 可以根据数据范围来排除一些问题。
- 编码：
- 想好总框架，想好实现，再写代码。
- 做好无经验实现的准备。
- 从大往小写。
- 调试：
- 造样例 + 中间过程输出。
- 二分法快速定位错误目标。
- 输出哪些信息很重要。
- 如果会对拍，那么会更好。
- 检查：
- 检查语法版本问题。
- 检查初始化和数组规模问题。
- 检查文件夹建立问题。
- 检查大样例正确性。
- 检查调试代码是否关闭。
- 比赛策略/心态建设：
- 部分分很重要。
- 策略根据情况（完成情况、剩余时间、题目的）
- 分数并不代表排名，不要被过度影响。
- 一定要留时间，不要一味追分。
考后的调整：
- 估分可以，但是找对人。
- 分数高低无所谓，比例才是最重要的。
- 记得复盘。
最后的几天如何备赛：
- 没刷真题的、看看真题熟悉难度（对应得分点的难度）。
- 根据自身能力，提前给一个大概的比赛策略。
- 一定要搞清楚对应地区的机器环境、防止出现一些奇怪的爆零问题。
- 拒绝高强度复习增加压力，以回顾和低烈度训练为主。
- 做好考前心理建设，考好考不好都要有心理准备。

std二分

std::binary_search：二分查找。

binary_search(v.begin(), v.end(), value)，其中 value 为需要查找的值。
std::lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。

lower_bound(v.begin(),v.end(),x)
std::upper_bound：在一个有序序列中进行二分查找，返回指向第一个大于 x 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。

upper_bound(v.begin(),v.end(),x)

int a[20] = {0, 1, 2, 4, 5, 5, 6, 7, 8, 10, 10};
cout << binary_search(a+1, a+10, 5) << endl;
cout << lower_bound(a+1, a+10, 5) - a << endl;
cout << upper_bound(a+1, a+10, 5) - a << endl;

out

ture 4 6

BFS

伪代码

bfs(s)
{
    queue<> q;
    q.push(s); vis[s] = true;
    while(!q.empty())
    {
        u = q.front();
        q.pop()
        for(v : e[u])
            if(!vis[v])
                q.push(v),
                vis[v] = true;
    }
}

最短路

oiwiki: https://oiwiki.com/graph/shortest-path/

朴素 Dijkstra

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 1e5+5;
const int INF = (1<<31)-1;

struct Edge{int v, w;};
vector<Edge> e[MAX];
int n, m, s, vis[MAX], dis[MAX];

void dijkstra()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    for(int i=1; i<=n; i++)
    {
        int u=0, mind=INF;
        for(int j=1; j<=n; j++)
            if(!vis[j] && dis[j] < mind)
                u = j, mind = dis[j];
        vis[u] = 1;
        for(auto t : e[u])
            dis[t.v] = min(dis[t.v], dis[u] + t.w);
    }
}

signed main()
{
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    dijkstra();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

Dijkstra 优化

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 2e5+5;
const int INF = (1<<31)-1;

struct Edge{
    int v, w;
    bool operator>(const Edge& a) const {return w > a.w;}
};
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
vector<Edge> e[MAX];
int n, m, s, vis[MAX], dis[MAX];

void dijkstra()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;
    q.push({s, 0});

    while(!q.empty())
    {
        int u = q.top().v;
        q.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        for(auto t : e[u])
            if (dis[t.v] > dis[u] + t.w) 
                dis[t.v] = dis[u] + t.w, 
                q.push({t.v, dis[t.v]});
    }
}

signed main()
{
    cin >> n >> m >> s;

    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
    }
    dijkstra();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

Bellman Ford

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX = 1e5+5;
const int INF = (1<<31)-1;

struct Edge{int u, v, w;};
vector<Edge> e;
int n, m, s, dis[MAX];

bool bellman_ford()
{
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[s] = 0;

    bool flag = 0; // 判断一轮循环过程中是否发生松弛操作
    for(int i=1; i<=n; i++)
    {
        flag = false;
        // 对每一条边进行松弛操作
        for(auto t : e)
        {
            // 最短路长度为 INF 的点引出的边不可能发生松弛操作
            if(dis[t.u] == INF) continue;
            if(dis[t.v] > dis[t.u] + t.w)
                dis[t.v] = dis[t.u] + t.w,
                flag = true; 
        }
        // 没有可以松弛的边时就停止算法
        if(flag == false) break;
    }
    // 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
    return flag;
}
signed main()
{
    cin >> n >> m >> s;
    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back((Edge){u, v, w});
    }
    bellman_ford();
    for(int i=1; i<=n; i++) cout << dis[i] << ' ';

    return 0;
}

Floyd

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, f[105][105];

void floyd()
{
    for(int k=1; k<=n; k++)
        for(int x=1; x<=n; x++)
            for(int y=1; y<=n; y++)
                f[x][y] = min(f[x][y], f[x][k]+f[k][y]);
}

int main()
{
    freopen("f.in", "r", stdin);
    cin >> n >> m;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) f[i][i] = 0;

    for (int i = 0; i < m; i++) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[v][u], w);
    }
    floyd();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cout << f[i][j] << " ";
        cout << endl;
    }
    return 0;
}

单调队列与单调栈

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e6+5;
int a[MAX];

signed main()
{
    int n, k; cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    deque<int> dq;
    for(int i=1; i<=n; i++) // 维护单调递减
    {
        while(!dq.empty() && dq.front() + k <= i) dq.pop_front(); // 淘汰太老的
        while(!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // 淘汰更老且大的
        dq.push_back(i);
        if(i >= k) cout << a[dq.front()] << " "; // 队首一定最小
    }
    cout << endl;
    dq.clear();
    for(int i=1; i<=n; i++) // 维护单调递增
    {
        while(!dq.empty() && dq.front() + k <= i) dq.pop_front(); // 淘汰太老的
        while(!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back(); // 淘汰更老且小的
        dq.push_back(i);
        if(i >= k) cout << a[dq.front()] << " "; // 队首一定最大
    }

    return 0;
}

并查集

高效处理集合的合并与查询。

#include<iostream>
using namespace std;

int fa[100005];
// 查询x节点的根节点编号
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

// 合并a、b所在集合
void merge(int a, int b) {fa[find(a)] = fa[find(b)];}

// 初始化n个集合
void init(int n) {for(int i=0;i<=n;i++) fa[i] = i;}

最小生成树

Kruskal

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
int fa[MAX], n, m, k;
struct Edge{int u, v, w;} g[MAX];

int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int a, int b) {fa[find(a)] = fa[find(b)];}
void init(int n) {for(int i=0; i<=n; i++) fa[i] = i;}
bool cmp(Edge a, Edge b) {return a.w < b.w;}

void kruskal()
{
    int total = 0; // 已选了的边数
    int ans = 0; // 总的代价
    for(int i=1; i<=m; i++)
        if(find(g[i].u) != find(g[i].v))
        {
            merge(g[i].u, g[i].v);
            total ++;
            ans += g[i].w;
            if(total == n - k) {cout << ans; return;}
        }
    cout << "No Answer";
}

int main()
{
    cin >> n >> m >> k;
    if(n == k) {cout << 0; exit(0);}
    init(n);
    for(int i=1; i<=m; i++)
        cin >> g[i].u >> g[i].v >> g[i].w;
    sort(g+1, g+m+1, cmp);
    kruskal();
    return 0;
}

Prim

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v, w;
    bool operator>(const Edge& a) const {return w > a.w;}
};
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
vector<Edge> e[MAX];
int n, m, k, vis[MAX], dis[MAX], cnt=0, ans=0;

void prim()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; q.push({1, 0});

    while(!q.empty())
    {
        if(cnt >= n) break;
        int u = q.top().v, w = q.top().w;
        q.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        ++cnt, ans += w;
        for(auto t : e[u])
            if (t.w < dis[t.v]) 
                dis[t.v] = t.w, q.push({t.v, t.w});
    }
}

signed main()
{
    cin >> n;

    for(int i=1; i<=n; i++)
    {
        int u, v;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    prim();
    if(cnt == n) cout << ans;
    else cout << "No MST";

    return 0;
}

拓扑排序

Kahn

#include<bits/stdc++.h>
using namespace std;

const int MAX = 105;
queue<int> q;
vector<int> g[MAX], ans;
int rd[MAX], n;

void kahn()
{
    for(int i=1; i<=n; i++)
        if(rd[i] == 0) q.push(i);
    while(!q.empty())
    {
        int t = q.front(); q.pop();
        ans.push_back(t);
        for(auto v : g[t])
        {
            rd[v]--;
            if(rd[v] == 0) q.push(v);
        }
    }
    if(ans.size() != n) cout << "有环" << endl;
    else for(auto v : ans) cout << v << ' ';
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int a; cin >> a;
        while(a) {g[i].push_back(a), rd[a]++; cin >> a;}
    }
    kahn();
    return 0;
}

DFS

#include<bits/stdc++.h>
using namespace std;
const int MAX = 105;
vector<int> e[MAX];
int n, vis[MAX];

stack<int> ans;
void dfs(int u)
{
    for(auto v : e[u]) {if(vis[v]) continue; dfs(v);}
    vis[u] = 1; ans.push(u);
}

signed main()
{
    int n, a; cin >> n;
    for(int i=1; i<=n; i++)
        while(cin >> a && a)
            e[i].push_back(a);
    for(int i=1; i<=n; i++) if(!vis[i]) dfs(i);
    while(!ans.empty()) cout << ans.top() << ' ', ans.pop(); 
    return 0;
}

DP（部分完成）

背包DP

// 在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。
for(int i=1; i<=n; i++)
    for(int j=W; j>=w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

多重背包二进制分组优化

int cnt = 0; // 二进制分组后的物品数量
for(int i=1; i<=n; i++)
{
    int v_i, w_i, m_i; 
    cin >> v_i >> w_i >> m_i;
    for(int j=1; j<=m_i; j<<=1) // 二进制分组优化
        v[++cnt] = j * v_i, w[cnt] = j * w_i, m_i -= j;
    if(m_i) v[++cnt] = v_i * m_i, w[cnt] = w_i * m_i; // 剩余部分
}

区间DP（未完成）

DAG上DP（未完成）

https://oiwiki.com/dp/dag/

状压DP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
const int M = 21;
int n, dp[N], dis[M][N];

int solve()
{
    for(int i=0; i < (1ll << n); i++) // 枚举状态（前驱状态 < 当前状态）
        for(int a=1, wa=1; a<=n; a++, wa<<=1) // 点编号为a，对应二进制位的值为 wa
            for(int b=1, wb=1; b<=n; b++, wb<<=1)
                if(a != b && (wa & i) == 0 && (wb & i) == 0) // b 没出现过
                    dp[i | wa | wb] = max(dp[i | wa | wb], dp[i]+dis[a][b]);
    return *max_element(dp, dp + (1ll << n));
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            cin >> dis[i][j], dis[j][i] = dis[i][j];
    cout << solve() << endl;

    return 0;
}

树形DP（未完成）

强连通分量

Kosraju

```cpp
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
vector<int> g1[MAX], g2[MAX], kos;
int vis[MAX], scc[MAX], n, m, scc_cnt=0;

void dfs1(int u)
{
    vis[u] = 1;
    for(auto v : g1[u])
        if(!vis[v]) dfs1(v);
    kos.push_back(u);
}

void dfs2(int u)
{
    scc[u] = scc_cnt;
    for(int v : g2[u])
        if(scc[v] == 0) dfs2(v);
}

void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    reverse(kos.begin(), kos.end());

    for(auto x : kos)
        if(scc[x] == 0) ++scc_cnt, dfs2(x);
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a, b; cin >> a >> b;
        g1[a].push_back(b);
        g2[b].push_back(a);
    }

    kosaraju();
    int cnt[MAX]; for(int i=1; i<=n; i++) cnt[scc[i]]++;
    int ans = 0;
    for(int i=1; i<=scc_cnt; i++)
        if(cnt[i] > 1) ans++;
    cout << ans;
    return 0;
}

缩点

int in[MAX], out[MAX];
set<int> edge[MAX];
void get_graph()
{
    for(int u=1; u<=n; u++)
    {
        int x = scc[u];
        scc_num += 1; // 点信息
        for(auto v : g1[u])
        {
            int y = scc[v];
            if(x != y) edge[x].insert(y), in[y] ++, out[x] ++; // 外部边信息
        }
    }
}

倍增

LCA

void dfs(int u, int f, int depth)
{
    fa[u][0] = f;
    dep[u] = depth;
    for(int i=1; i<=30; i++) 
        fa[u][i] = fa[fa[u][i-1]][i-1];

    for(auto i : e[u])
        if(i != f) dfs(i, u, depth+1);
}

int up(int x, int h)
{
    int i=0;
    while(h)
    {
        if(h & 1) x = fa[x][i];
        h >>= 1;
        i++;
    }
    return x;
}

int LCA(int a, int b)
{
    if(dep[a] < dep[b]) swap(a, b);
    a = up(a, dep[a]-dep[b]);
    if(a == b) return a; // attention;

    for(int i=30; i>=0; i--)
        if(fa[a][i] != fa[b][i])
            a = fa[a][i],
            b = fa[b][i];

    return fa[a][0];
}

ST表

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e6+5;
const int LOGMAX = 25;
int st[MAX][LOGMAX], logn[MAX];

void preLog()
{
    logn[1] = 0;
    logn[2] = 1;
    for(int i=3; i<MAX; i++) logn[i] = logn[i/2]+1; 
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    // 长度为1的区间最大值就是元素本身
    for(int i=1; i<=n; i++) cin >> st[i][0];
    // preLog();
    // 递推构建ST表: 
    // st[i][j] = max(st[i][j-1], st[i+2^(j-1)][j-1])
    for(int j=1; (1<<j) <= n; j++)
        for(int i=1; i+(1<<j)-1 <= n; i++)
            st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]);

    for(int i=1; i<=m; i++)
    {
        int l, r; cin >> l >> r;
        int s = log2(r - l + 1); // s = logn[r - l + 1];
        cout << max(st[l][s] ,st[r-(1<<s)+1][s]) << endl;
    }
    return 0;
}

快速幂

long long p;
long long ksm(long long a, long long b)
{
    long long ans = 1;
    while(b)
    {
        if(b & 1) ans *= a, ans %= p;
        a *= a; a %= p;
        b >>= 1;
    }
    return ans;
}

字符串哈希

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int P = 131;
ULL v[10005];

ULL value(string s)
{
    ULL ans=s[0];
    for(int i=1; i<s.size(); i++) ans = ans*P + s[i];
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin >> s;
        v[i] = value(s);
    }

    sort(v+1, v+n+1);
    int ans = 0;
    for(int i=1; i<=n; i++)
        if(v[i] != v[i+1]) ans ++;
    cout << ans;
    return 0;
}

离散化（未完成）

树上算法（未完成）

树状数组

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 5e5+5;
int a[MAX], t[MAX], n, m;

int lowbit(int x) {return x & -x;}
void add(int u, int v)
{
    while(u <= n)
        t[u] += v,
        u += lowbit(u);
}
int sum(int u)
{
    int ans = 0;
    while(u)
        ans += t[u],
        u -= lowbit(u);
    return ans;
}
int sum(int x, int y) {return sum(y) - sum(x-1);}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) {cin >> a[i]; add(i, a[i]);}
    for(int i=0;i<m;i++)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if(opt == 1) add(x, y);
        else if(opt == 2) cout << sum(x, y) << endl;
    }
    return 0;
}

线段树

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int MAX = 1e5+5;
struct Segment_Tree
{
    int l, r;
    long long tag, val;
}tree[MAX << 2];
int n, m, val[MAX];
inline int ls(int x) {return x << 1;}
inline int rs(int x) {return x << 1 | 1;}
inline bool out(int u, int l, int r) {if(tree[u].l > r || tree[u].r < l) return 1; return 0;}
inline bool in(int u, int l, int r) {if(tree[u].l >= l && tree[u].r <= r) return 1; return 0;}
inline void pushup(int u) {if(tree[u].l != tree[u].r) tree[u].val = tree[ls(u)].val + tree[rs(u)].val;}
inline void pushdown(int u)
{
    if(tree[u].l == tree[u].r) return;
    if(tree[u].tag)
    {
        tree[ls(u)].tag += tree[u].tag;
        tree[ls(u)].val += (tree[ls(u)].r - tree[ls(u)].l + 1) * tree[u].tag;
        tree[rs(u)].tag += tree[u].tag;
        tree[rs(u)].val += (tree[rs(u)].r - tree[rs(u)].l + 1) * tree[u].tag;
        tree[u].tag = 0; // *
    }
}

int query(int u, int l, int r)
{
    if(out(u, l, r)) return 0;
    if(in(u, l, r)) return tree[u].val;
    pushdown(u);
    return query(ls(u), l, r) + query(rs(u), l, r);
}

void modify(int u, int l, int r, int x)
{
    if(out(u, l, r)) return;
    if(in(u, l, r)) tree[u].tag += x, tree[u].val += (tree[u].r - tree[u].l + 1) * x;
    else
    {
        pushdown(u);
        modify(ls(u), l, r, x);
        modify(rs(u), l, r, x);
        pushup(u);
    }
}

void build(int u, int l, int r)
{
    tree[u].l = l;
    tree[u].r = r;
    if(l == r) {tree[u].val = val[l]; return;}

    int mid = (l + r) >> 1;
    build(ls(u), l, mid);
    build(rs(u), mid+1, r);
    pushup(u);
}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> val[i];
    build(1, 1, n);

    while(m--)
    {
        int x, y, op, k;
        cin >> op;
        if(op == 1) {cin >> x >> y >> k; modify(1, x, y, k);}
        else {cin >> x >> y; cout << query(1, x, y) << endl;}
    }

    return 0;
}