值域线段树每一个节点代表一个值，其他没什么区别
动态开树就是节省了没有用到节点，其中重要一点的是不需要节点是连续的（即id值是任意的，只要可以找到即可）
例题
Bzoj 4627 回转寿司
题意
给n个数问区间和在L<=sum【r】-sum【l-1】<=R区间有多少个
（N≤100000，|Ai|≤100000，0≤L, R≤10^9）
分析
由于区间和不单调，所以不能二分求取，分析可得推出公式 sum(r)-R<=sum(l-1)<=sum(r)-L （[l,r]是一个满足条件的区间）
直接计算当前前缀和之前满足条件的前缀和个数，累加起来则为答案
故考虑利用线段树，每次让对应的前缀和加1，然后统计满足条件的个数，但是这个数最大可以达到1e10，不可能开这么大的空间，
但N最大10w，和的种类也就10w，故考虑动态开线段树，每次只开根到这个节点上路径上经过的点，这样最多开log（N）*N即可，
这样的话每次必须保存当前节点的左右儿子的id才可以准确访问左右儿子，其他和线段树差不多
trick：注意开始要处理sum【0】，这样才可以保证当l==r时满足条件也能被统计上
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e7 + 10; ll tree[maxn], lson[maxn], rson[maxn]; ll tot; ll a[100005]; ll sum[100005]; const ll inf = 1e10; int n; ll root=1; int newnode() { ++tot; tree[tot] = lson[tot] = rson[tot] = 0; return tot; } void update(ll &x, ll l, ll r, ll val) { if(!x) x=newnode(); tree[x]++; if(l == r) return; ll mid = (l+r)>>1; if(val<=mid ) update(lson[x], l, mid, val); else update(rson[x], mid+1, r, val); } ll query(ll x, ll l, ll r, ll ql, ll qr) { if(ql<=l && qr>=r) return tree[x]; ll mid = (l + r)>> 1; ll ans = 0; if(ql<=mid && lson[x]) ans +=query(lson[x], l , mid, ql, qr); if(qr>mid && rson[x]) ans+=query(rson[x], mid+1, r, ql, qr); return ans; } int main() { ll n, l ,r; scanf("%lld%lld%lld", &n, &l, &r); for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); sum[i]=sum[i-1]+a[i]; } ll ans=0; update(root, -inf, inf, 0); for(int i = 1; i<=n;i++) { ans+=query(root, -inf, inf, sum[i]-r, sum[i]-l); update(root,-inf,inf,sum[i]); } printf("%lld ", ans); return 0; }