【模板】线段树

计蒜客：

注：计蒜客相关解释十分清晰，不清楚的代码可直接看分析

基础：

对线段树区间的理解+对结点个数的理解

O(n)地递归建立线段树（代码实现）

O(logn)单点修改（代码实现） O(logn)单点查询

O(logn)区间查询（代码实现）

进阶：(lazy标记)

O(logn)区间修改（代码实现）

O(logn)区间查询（不同于上面的区间查询哦）（代码实现）

有lazy的地方保证权值正确，它的下一个地方权值才是不正确的

部分基础代码

#include <iostream>
using namespace std;
const int inf_ = 0x3f3f3f3f;
const int maxN_ = 110;
int a[maxN_];
class BinaryIndexedTree_ {
public:
  #define lId id << 1
  #define rId id << 1 | 1
  #define mid_ int mid = (l + r) >> 1
  int minv[4 * maxN_];
  void PushUp(int id) { minv[id] = min(minv[lId], minv[rId]); }
  void Build(int id, int l, int r) {
    if (l == r) {
      minv[id] = a[l];
      return;
    }
    mid_;
    Build(lId, l, mid);
    Build(rId, mid + 1, r);
    PushUp(id);
  }
  void UpDate(int id, int l, int r, int x, int v) {
    if (l == r) {
      minv[id] = v;
      return;
    }
    mid_;
    if (x <= mid) {
      UpDate(lId, l, mid, x, v);
    } else {
      UpDate(rId, mid + 1, r, x, v);
    }
    PushUp(id);
  }
  int Query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
      return minv[id];
    }
    mid_;
    int ans = inf_;
    if (x <= mid) {
      ans = min(ans, Query(lId, l, mid, x, y));
    }
    if (y > mid) {
      ans = min(ans, Query(rId, mid + 1, r, x, y));
    }
    return ans;
  }
} bit;
int main() {
  int n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  bit.Build(1, 1, n);
  int q;
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int x, v;
    cin >> x >> v;
    bit.UpDate(1, 1, n, x, v);
  }
  int p;
  cin >> p;
  for (int i = 0; i < p; ++i) {
    int l, r;
    cin >> l >> r;
    cout << bit.Query(1, 1, n, l, r) << endl;
  }
  return 0;
}

View Code

基础部分代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <iostream>
#include <stack>
using namespace std;

///-------------------------------------------------------常用规定部分
//----------------------便于更改
// nodeType(1~1e7) 都是int就不必麻烦了
#define valueType_ int // valueType(1~1e19)
//----------------------通用
#define inf_ 0x3f3f3f3f //这是给int的inf，值为1061109567，2^31-1为2147483647
#define reg_ register int
#define for_(i, n) for (int i = 1; i <= n; i++)
#define forReg_(i, n) for (reg_ i = 1; i <= n; i++)
#define ll_ long long
#define ull_ unsigned long long
//----------------------其它
const int maxN_ = 1e2 + 10;
const int maxM_ = 1e4 + 10;
///-------------------------------------------------------变量声明部分
//--------------------------------------其它
int a[maxN_];
class SEGMENT_TREE {
public:
  //宏定义
#define mid_ int mid = (l + r) >> 1 // mid的定义
#define len_ (r - l + 1)
#define lId_ id << 1
#define rId_ id << 1 | 1
#define lSon_ id << 1, l, mid
#define rSon_ id << 1 | 1, mid + 1, r
#define include_(x, y, l, r) x <= l &&r <= y
  // data
  int minv[4 * maxN_], lazy[4 * maxN_];
  // function
  void PushUp(int id) { minv[id] = min(minv[lId_], minv[rId_]); }
  void PushDown(int id) {
    if (lazy[id]) {
      lazy[lId_] += lazy[id];
      lazy[rId_] += lazy[id];
      minv[lId_] += lazy[id];
      minv[rId_] += lazy[id];
      lazy[id] = 0;
    }
  }
  void Build(int id, int l, int r) {
    if (l == r) {
      minv[id] = a[l];
      return;
    }
    mid_;
    Build(lSon_);
    Build(rSon_);
    PushUp(id);
  }
  void UpDate(int id, int l, int r, int x, int y, int v) {
    if (x <= l && r <= y) {
      lazy[id] += v;
      minv[id] += v;
      return;
    }
    PushDown(id);
    mid_;
    if (x <= mid) {
      UpDate(lSon_, x, y, v);
    }
    if (y > mid) {
      UpDate(rSon_, x, y, v);
    }
    PushUp(id);
  }
  int Query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
      return minv[id];
    }
    PushDown(id);
    mid_;
    int ans = inf_;
    if (x <= mid) {
      ans = min(ans, Query(lSon_, x, y));
    }
    if (y > mid) {
      ans = min(ans, Query(rSon_, x, y));
    }
    return ans;
  }
} tree;
///--------------------------------------------------------函数声明部分
//--------------------------------------其它

///--------------------------------------------------------main函数部分
int main() {
  // freopen("in.txt","r", stdin);
  // freopen("out.txt","w", stdout);
  ios::sync_with_stdio(false);
  // InitEdge();
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  tree.Build(1, 1, n);
  int q;
  cin >> q;
  while (q--) {
    int x, y, v;
    cin >> x >> y >> v;
    tree.UpDate(1, 1, n, x, y, v);
  }
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    cout << tree.Query(1, 1, n, x, y) << endl;
  }
  return 0;
}
///--------------------------------------------------------函数定义部分
//----------------------------------其它
/*
data:
5
1 2 3 4 5
2
1 5 1
2 4 -4
2
1 5
5 5
ans:
-1
5
*/

View Code