单链表 —— 模板题 AcWing 826. 单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}
双链表 —— 模板题 AcWing 827. 双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}
栈 —— 模板题 AcWing 828. 模拟栈
// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0)
{

}
队列 —— 模板题 AcWing 829. 模拟队列
1. 普通队列：
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}
2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}
单调栈 —— 模板题 AcWing 830. 单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}
单调队列 —— 模板题 AcWing 154. 滑动窗口
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}
KMP —— 模板题 AcWing 831. KMP字符串
求Next数组：
// s[]是模式串，p[]是模板串, n是s的长度，m是p的长度
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}
Trie树 —— 模板题 AcWing 835. Trie字符串统计
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
并查集 —— 模板题 AcWing 836. 合并集合, AcWing 837. 连通块中点的数量
(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    size[b] += size[a];


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[I] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
堆 —— 模板题 AcWing 838. 堆排序, AcWing 839. 模拟堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
一般哈希 —— 模板题 AcWing 840. 模拟散列表
(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }
字符串哈希 —— 模板题 AcWing 841. 字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
C++ STL简介
vector, 变长数组，倍增的思想//每当空间不够时将当前空间乘以二
    vector<int> a(n); //(n,2) 长n数为二
n长度---longn 时间
    size()  返回元素个数/
    empty()  返回是否为空/o(1)所有stl都有
    clear()  清空//vector<int>v(0);
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序
lower_bound()/upper_bound()
            lower_bound(b,e,x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    去重：
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for(vector<int>:: iterator i = a.begin(); i != a.end(); ++i)  cout<<*i;
    for(auto x : a)cout<<x<<endl;
pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
    pair<int,int> p;
    p = make_pair(10,2);
    P = {10,2}; //C11 

string，字符串
string是动态大小的，可以自动调整大小以容纳不同长度的字符串。
reverse(s.begin(),s.end());//将字符串开头和结尾反转.
string str = s.substr(pos,n);//截取字符串s中pos位置开始的长度为n的字符串
s.erase(pos1,pos2); //删除字符串s中从位置pos1到位置pos2间的字符
 string c(5, ' '); // 初始化为长度为5的空格字符串
    size()/length()  返回字符串长度
    string s;
    getline(cin, s);//读一行
    empty()
    find()
    clear()
    substr(起始下标，(子串长度))  返回子串a.substr(0,2);
    c_str()  返回字符串所在字符数组的起始地址  printf("%s",a.c_str());
    string a = "12";
    a += "2"; c_str
queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素//非top();
    back()  返回队尾元素
    pop()  弹出队头元素
   无clear() q = queue<int>();  
priority_queue, 优先队列，默认是大根堆
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素 //无clear();

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []
sort(q.begin(), q.end())//从小到大
sort(q.begin(), q.end(), greater<int>());//从大到小排序

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset,bool 圧位 将字节压于位/8 ， 
    bitset<10000> s; //<>：个数 ；bitset 整数
    ~, &, |, ^
    >>, <<
    ==, !=
    []
    count()  返回有多少个1
    any()  判断是否至少有一个1
    none()  判断是否全为0
    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

memset: 字节赋值 ：int a[ 2 ] ; memest (a, ox3f , sizeof(a) )  - > 四字节同为（0x3f）- > 0x3f3f3f3f; 
memset(a,0/- 1,sizeof(a)); 0 - > 0000 ； -1- > 1111;

sort(begin, end, greater<data-type>())；
sort(a, a + 10,greater<int>());

sort(c.begin(),c.end(),comp);（vector<double>c）
bool comp(const double &a, const double &b){
//常引用const T &xxx
    return a< b;
    //<代表升序，>代表降序
}

struct A{
int x,y;
bool operator<(const A &a)const{
if(x==a.x) {return y<a.y;}
else {return x<a.x;}  }
}
printf("%s\%c\%lf\%lld%u\%llu");
自动四舍五入;
%4.0f ->4是指输出时的位宽(有数字位)为4;
 闰年:非100整除且能被4整除的年份,或被400整除的;  2月分,多一天29天

 printf(“%04d”,a)    ->0补位
  scanf("%d%*c%d",&a,&b); // in (2"3) out(2,3) 
sacnf("%d-%d",&a,&b); //in(2-3) out(2,3);
    printf("%d,%d",a,b);
tolower(‘’); toupper(‘’);//字符
vector<vector<int> > vec2 (n,vector<int>(m,0))  //开一个n行m列,初始为0
    vector<int> x(n,0)=== vector<int> x(n);

快读 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
向下取整（不大于x的最大整数）floor() 
向上取整（不小于x的最小整数）ceil() 函数
四舍五入 round() 函数

进制转化
    cout<<"300的8进制："  <<std::oct <<300<<endl;   //按八进制格式输出
    cout<<"300的10进制：" <<std::dec <<300<<endl;   //按十进制格式输出
    cout<<"300的16进制：" <<std::hex <<300<<endl;   //按十六进制格式输出
    cout<<"300的2进制："  <<bitset<8>(300)<<endl;    //<8>：表示保留8位输出

int binary(int m, string s){ //转10
    int ans=0;
    for(int i=0;i<s.size();i++){
        char t=s[i];
        if(t>='0'&&t<='9') 
            ans=ans*m+t-'0';
        else 
            ans=ans*m+t-'a'+10;
    }
    return ans;
}
long int strtol(const char *nptr, char **endptr, int base)
 base是要转化的数的进制，非法字符会赋值给endptr，nptr是要转化的字符，例如:
 char buffer[20]="10549stend#12";  
    char *stop;  
    int ans=strtol(buffer, &stop, 8);   //将八进制数1054转成十进制，后面均为非法字符
    printf("%d\n",ans);  556
    printf("%s\n", stop); 9stend#12

string intToA(int n,int m){//10转m;
    string ans="";
    do{      //使用do{}while()循环类型以防止输入为0的情况
        int t=n%m;
        if(t>=0&&t<=9)    
            ans+=(t+'0');
        else 
            ans+=(t+'a'-10);
        n/=m;
    }while(n);   
    reverse(ans.begin(),ans.end());
    return ans;    
}
 函数原型：char*itoa(int value,char*string,int radix);
    int num = 10;  
    char str[100];  
    _itoa(num, str, m);  //c++中一般用_itoa，用itoa也行,10转m;

    printf("%s\n", str); 
    int intStr = atoi(str.c_str()); atol(long long ) //(str)string - >int
to_string(number); int - > string;

int la = strlen(a + 1), lb = strlen(b + 1); char a[];cin>>a+1;
strlen(char*)函数求的是字符串的实际长度
//备份
memcpy(a,b,sizeof b); b -> a

int v[n1][k] 中的 n1 和 k 必须在编译时是常量表达式。如果你想使用动态大小的二维数组，你可以使用 vector<vector<int>> v(n1, vector<int>(k)); 来代替。
sqrt()
unsigned
一秒可以处理1e8
1Mb = 1e6B = 1e7字节。

while (r - l > eps)//0.
    {
        double mid = (r - l) / 3.0;
        double m1 = l + mid;
        double m2 = m1 + mid;
        if (f(m1) < f(m2))
            l = m1;
        else
            r = m2;
    }

//线段树模板，longn修改某点值，快速求某区间和值
#include<bits/stdc++.h>

using namespace std;

const int maxn=100010;

int a[maxn+2];

struct tree{
    int l,r;
    long long pre,add;
}t[4*maxn+2];

void bulid(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].pre=a[l];
        return;
    }
    int mid=l+r>>1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    t[p].pre=t[p*2].pre+t[p*2+1].pre;
} 

void spread(int p){
    if(t[p].add){
        t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
        t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
        t[p*2].add+=t[p].add;
        t[p*2+1].add+=t[p].add;
        t[p].add=0;
    }
}

void change(int p,int x,int y,int z){
    if(x<=t[p].l && y>=t[p].r){
        t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
        t[p].add+=z;
        return;
    }
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(p*2,x,y,z);
    if(y>mid) change(p*2+1,x,y,z);
    t[p].pre=t[p*2].pre+t[p*2+1].pre;   
}

long long ask(int p,int x,int y){
    if(x<=t[p].l && y>=t[p].r) return t[p].pre;
    spread(p);
    int mid=t[p].l+t[p].r>>1;
    long long ans=0;
    if(x<=mid) ans+=ask(p*2,x,y);
    if(y>mid) ans+=ask(p*2+1,x,y);
    return ans;
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    bulid(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int q,x,y,z;
        scanf("%d",&q);
        if(q==1){
            scanf("%d%d%d",&x,&y,&z);
            change(1,x,y,z);
        }
        else {
            scanf("%d%d",&x,&y);
            cout<<ask(1,x,y)<<endl;
        }
    }
    return 0;
}