线段树~总结下吧

为什么我比较喜欢线段树呢

因为线段树容易写，万一写错了还容易调试

能以优秀的效率完成一些比较水的操作

如：

单点更新（增减， 替换等）O(logn)

查询区间（最值，求和等 ）O(logn)

但只能查询区间的话明显是不够的

而修改区间用单点更新的方法复杂度就不再优了

于是我们引进一种lazy标记， 也可以叫可持续化

这个时候再谈修改区间， 无论是替换， 增减， 求和， 异或就无压力了

至于区间的合并与离散化扫描线也不在话下

贴段code吧

我习惯写我最爱的大常数版堆式线段树

simple

#include <ctime>#include <cstdio>#include <cstdlib>#include <iostream>using namespace std;const int maxn = 100000 + 5;class Interval_tree{   public :      Interval_tree()      {         memset(a, 0, sizeof(a));         memset(l, 0, sizeof(l));         memset(r, 0, sizeof(r));         memset(lazy, 0, sizeof(lazy));      }      void pushup(int rt)      {         a[rt] = a[rt << 1] + a[rt << 1 | 1];      }      void pushdown(int rt, int wh)      {         if (lazy[rt] != 0)         {            lazy[rt << 1] += lazy[rt];            lazy[rt << 1 | 1] += lazy[rt];            a[rt << 1] += lazy[rt] * (wh - (wh >> 1));            a[rt << 1 | 1] += lazy[rt] * (wh >> 1);            lazy[rt] = 0;         }      }      void buildtree(int rt)      {         if (l[rt] == r[rt])         {            scanf("%lld", &a[rt]);            return;         }         int mid = (l[rt] + r[rt]) >> 1;         l[rt << 1] = l[rt];         r[rt << 1] = mid;         l[rt << 1 | 1] = mid + 1;         r[rt << 1 | 1] = r[rt];         if (l[rt] <= mid) buildtree(rt << 1);         if (r[rt] > mid) buildtree(rt << 1 | 1);         pushup(rt);      }      void Insert(int x, int y, int k, int rt)      {         if (x <= l[rt] && y >= r[rt])         {            lazy[rt] += k;            a[rt] += (long long)k * (r[rt] - l[rt] + 1);            return;         }         pushdown(rt, r[rt] - l[rt] + 1);         int mid = (l[rt] + r[rt]) >> 1;         if (x <= mid) Insert(x, y, k, rt << 1);         if (y > mid) Insert(x, y, k, rt << 1 | 1);         pushup(rt);      }      long long Query(int x, int y, int rt)      {         if (x <= l[rt] && y >= r[rt])            return a[rt];         pushdown(rt, r[rt] - l[rt] + 1);         int mid = (l[rt] + r[rt]) >> 1;         long long ans = 0;         if (x <= mid) ans += Query(x, y, rt << 1);         if (y > mid) ans += Query(x, y, rt << 1 | 1);         return ans;      }      void initialize()      {         cin >> n >> m;         l[1] = 1; r[1] = n;         buildtree(1);         for (int i = 1; i <= m; ++i)         {            char ch; int x, y, k;            scanf("\n%c", &ch);            if (ch == 'Q')            {               scanf("%d%d", &x, &y);               long long Ans = Query(x, y, 1);               printf("%lld\n", Ans);            }            else if (ch == 'C')            {               scanf("%d%d%d", &x, &y, &k);               Insert(x, y, k, 1);            }         }      }   private :      int n, m;      long long a[maxn << 2];      int l[maxn << 2], r[maxn << 2];      long long lazy[maxn << 2];};Interval_tree interval_tree;int main(){   freopen("simple.in", "r", stdin);   freopen("simple.out", "w", stdout);   interval_tree.initialize();   return 0;}

另吐槽下cuizimu奇葩的类写法， 在类内声明， 要封装的函数全写外面。

且还用drj的写法和我一样的神D来D我。