[线段树]4.5撕心裂肺的一天

月考，清明都结束了

失踪人口的回归

短时间内应该没有什么要紧的事了

但是篮球赛，春游，文化周又来了

今天打篮球在场下喊得撕心裂肺

真是美好的少年时光啊

索性讲一下线段树好了

先放湿乎乎dalao的博客

开启了我线段树的大门

《数据结构》线段树入门（一）

《数据结构》线段树入门（二）

对此表示深深的感谢

　　　　　　　　　　以下是正文部分　　　　　　　　　　

一.什么是线段树？

 

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　百度百科

二.线段树是干什么的？

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　百度百科

 三.贴完代码就跑，详解下回再说

#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int val[N];
struct tree
{
int l,r;
long long sum,add;
}tr[N<<2];
void build(int q,int w,int i)
{
    tr[i].l=q,tr[i].r=w;
if (q==w) tr[i].sum=val[q];
else
    {
long long  mid=(tr[i].l+tr[i].r)>>1;
        build (q,mid,i<<1);
        build (mid+1,w,i<<1|1);
        tr[i].sum=tr[i<<1].sum+tr[i<<1|1].sum;
    }

}
void pushdown (int i,int m)
{
if (tr[i].add)
    {
        tr[i<<1].add+=tr[i].add;
        tr[i<<1|1].add+=tr[i].add;
        tr[i<<1].sum+=tr[i].add*(m-(m>>1));
        tr[i<<1|1].sum+=tr[i].add*(m>>1);
        tr[i].add=0;
    }
}
void update(int q,int w,int i,int x)
{
if (q<=tr[i].l&&w>=tr[i].r) 
    {
        tr[i].add+=x,tr[i].sum+=x*(tr[i].r-tr[i].l+1);
return ;
    }
else
    {
        pushdown (i,tr[i].r-tr[i].l+1);
long long  mid=(tr[i].l+tr[i].r)>>1;
if (q>mid) update (q,w,i<<1|1,x);
else if (w<=mid) update (q,w,i<<1,x);
else
        {
            update (q,w,i<<1|1,x);
            update (q,w,i<<1,x);
        }
        tr[i].sum=tr[i<<1].sum+tr[i<<1|1].sum;
    }
}
long long query (int q,int w,int i)
{
if (q<=tr[i].l&&w>=tr[i].r) return tr[i].sum;
else
    {
        pushdown (i,tr[i].r-tr[i].l+1);
long long  mid=(tr[i].l+tr[i].r)>>1;
if (q>mid) return query (q,w,i<<1|1);
else if (w<=mid) return query (q,w,i<<1);
else return query (q,w,i<<1|1)+query (q,w,i<<1);
    }
}
int main()
{
int n;
    scanf ("%d",&n);
for (int i=1;i<=n;i++)
    {
        scanf ("%d",&val[i]);
    }
    build (1,n,1);
int q;
    scanf ("%d",&q);
while (q--)
    {
int flag,a,b;
        scanf ("%d %d %d ",&flag,&a,&b);
if (flag==1) 
        {
int x;
            scanf ("%d",&x);
            update (a,b,1,x);
        }
else
        {
            printf ("%lld\n",query(a,b,1));
        }
    }
return 0; 
} 

 就是这样，喵~

---

最后一行献给在球场上挥洒汗水的男孩子们

---