[数据结构与算法]数据结构与算法-线段树模板

• 条件：求区间和，区间修改。

• 题目：洛谷线段树模板

• 原理：无

• 代码：

  /**
  * mootable
   */
  #include <iostream>
  #include <iomanip>
  #include <algorithm>  //sort
  #include <map>
  #include <queue>
  #include <deque>  //双端队列，头可插，尾可插
  #include <string>
  #include <cstring>
  #include <stack>
  #include <cmath>
  #include <fstream>
  #include <ctime>
  #include <climits> //数值的限制范围
  //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
  using namespace std;
  
  class Solver {
      //通用属性
  public:
      Solver() {
          //取消和c输出输入的同步，加快读取
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
          cout.tie(nullptr);
      }
  
      //通用方法
  public:
      void SaveCpp(string name) const {
  
          fstream input;
          fstream output;
  
          input.open("moota.cpp", ios::in);
          const string file = name + ".cpp";
          output.open(file.c_str(), ios::out);
  
          char c = 'O';
          while (!input.eof()) {
              input.get(c);
              output << c;
          }
  
          input.close();
          output.close();
  
      }
  
  protected:
      //待实现方法
      virtual void BeginPlay() {
      };
  
      virtual void Playing() {
      };
  
      virtual void EndPlay() {
      };
  public:
      //外观模式
      void Play() {
          BeginPlay();
          Playing();
          EndPlay();
      }
  };
  
  class SpecialSolver : public Solver {
  public:
      typedef long long lld;
      static const lld MAX = static_cast<lld>(1e6);
      static const lld INF = static_cast<lld>(1e18);
  private: //实例属性
      lld a[MAX];
  
      struct Tree {
          //区间范围
          lld l, r;
          //sum:区间和，add:待子节点增加的数值
          lld sum, add;
      } tree[4 * MAX];
  
      int n, m;
  private: //实例方法
      void Build(const lld id, const lld left, const lld right) {
          tree[id] = {left, right, 0, 0};
          //到达叶子节点
          if (left == right) {
              tree[id].sum = a[left];
              return;
          }
          const int mid = (left + right) / 2;
          Build(id * 2, left, mid);
          Build(id * 2 + 1, mid + 1, right);
          //回溯
          tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
      }
  
      void Spread(const lld id) {
          if (tree[id].add > 0) {
              const int left = id * 2;
              const int right = id * 2 + 1;
              tree[left].sum += (tree[left].r - tree[left].l + 1) * tree[id].add;
              tree[right].sum += (tree[right].r - tree[right].l + 1) * tree[id].add;
              tree[left].add += tree[id].add;
              tree[right].add += tree[id].add;
              tree[id].add = 0;
          }
      }
  
      void RangeAdd(const lld id, const lld left, const lld right, const lld value) {
          //完全覆盖区间
          if (left <= tree[id].l && tree[id].r <= right) {
              tree[id].sum += (tree[id].r - tree[id].l + 1) * value;
              tree[id].add += value;
          }
              //在子区间寻找完全覆盖区间
          else {
              //用到子区间需要下放懒人标记
              Spread(id);
              //左子树的右边界：见Build(id * 2, left, mid);
              const lld mid = (tree[id].l + tree[id].r) / 2; 
              //因为是找被left-right覆盖的区间，left，right不变
              if (left <= mid)RangeAdd(id * 2, left, right, value); 
              if (right > mid)RangeAdd(id * 2 + 1, left, right, value);
              tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
          }
      }
  
      lld RangeSum(const lld id, const lld left, const lld right) {
          if (left <= tree[id].l && tree[id].r <= right) {
              return tree[id].sum;
          }
          else {
              Spread(id);
              const lld mid = (tree[id].l + tree[id].r) / 2;
              lld sum = 0;
              if (left <= mid)sum += RangeSum(id * 2, left, right);
              if (right > mid)sum += RangeSum(id * 2 + 1, left, right);
              return sum;
          }
      }
  
  protected:
      virtual void BeginPlay() override {
          Solver::BeginPlay();
          cin >> n >> m;
          for (int i = 1; i <= n; ++i) {
              cin >> a[i];
          }
          Build(1, 1, n);
      };
  
      virtual void Playing() override {
          Solver::Playing();
          int order, x, y, k;
          while (m--) {
              cin >> order;
              switch (order) {
              case 1:
                  cin >> x >> y >> k;
                  RangeAdd(1, x, y, k);
                  break;
              case 2:
                  cin >> x >> y;
                  cout << RangeSum(1, x, y)<<"\n";
                  break;
              default:
                  cout << "未处理情况: " << order;
                  break;
              }
          }
      };
  
      virtual void EndPlay() override {
          Solver::EndPlay();
  
      };
  };
  
  SpecialSolver specialSolver;
  
  int main() {
      //注意改名字
      //specialSolver.SaveCpp("temp");
      specialSolver.Play();
  }