配合https://www.bilibili.com/video/av47331849食用
带node是tree的下标，不带node是arr下标
Note：下面模板中，更新范围lr和线段树范围 LR均是针对数组的大小而言，即范围在(0,arr.size()-1)之间
练习题：https://vjudge.net/contest/66989#overview
#include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<map> #include<unordered_map> #include<unordered_set> #include<set> #include<stack> #include<sstream> #include<fstream> #include<assert.h> #include<bitset> //#include<Eigen/Dense> //using namespace Eigen; using namespace std; const int maxn = 100000; int lz[maxn], tree[maxn], arr[maxn]; void build(int node, int start, int end) { if (start == end) { tree[node] = arr[start]; return; } int mid = (start + end) / 2; build(2 * node + 1, start, mid); build(2 * node + 2, mid + 1, end); tree[node] = tree[2 * node + 1] + tree[2 * node + 2]; } //单点更新将arr[idx]改为val void update(int node, int start, int end, int idx, int val) { if (start == end) { arr[idx] = val;//修改数组arr[idx]的值 tree[node] = val;//修改树种对应的值 return; } int mid = (start + end) / 2; int left_node = 2 * node + 1; int right_node = 2 * node + 2; if (idx >= start && idx <= mid) update(left_node, start, mid, idx, val); else update(right_node, mid + 1, end, idx, val); tree[node] = tree[left_node] + tree[right_node]; } //lazy操作相关 void push_down(int node, int l, int r) { if (lz[node]) { int mid = (l + r) / 2; lz[node * 2 + 1] += lz[node]; lz[node * 2 + 2] += lz[node]; tree[node * 2 + 1] += 1LL * (mid - l + 1)*lz[node]; tree[node * 2 + 2] += 1LL * (r - mid)*lz[node]; lz[node] = 0; } } // 区间更新，lr为更新范围，LR为线段树范围，add为区间整体增加值 void update_range(int node, int l, int r, int L, int R, int add) { if (l <= L && r >= R) { lz[node] += 1LL * add; tree[node] += 1LL * (R - L + 1)*add; // 更新方式 return; } push_down(node, L, R); int mid = (L + R) / 2; if (mid >= l) update_range(node * 2 + 1, l, r, L, mid, add); if (mid < r) update_range(node * 2 + 2, l, r, mid + 1, R, add); tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2]; } // 区间和查找，lr为查找范围，LR为线段树范围 long long query_range(int node, int l, int r ,int L, int R) { if (l <= L && r >= R) return tree[node]; push_down(node, L, R); int mid = (L + R) / 2; long long sum = 0; //当线段树范围[L,mid]和查找范围[l,r]有交集时 if (mid >= l) sum += query_range(node * 2 + 1, l, r, L, mid); if (mid < r) sum += query_range(node * 2 + 2, l, r, mid + 1, R); return sum; } //使用时，注意lazy数组的memset int main() { int tmp[] = { 1,3,5,7,6,11 }; memset(lz, 0, sizeof(lz)); int size = 6;//数组arr的元素数 for (int i = 0; i < size; i++) arr[i] = tmp[i]; build(0, 0, size - 1); //树中共16个元素 for (int i = 0; i < 15; i++) cout << i << " " << tree[i] << endl; cout << endl << endl; update_range(0, 2, 5, 0, 5, 1); for (int i = 0; i < 15; i++) cout << i << " " << tree[i] << endl; cout << endl << endl; return 0; }
