# 線段樹

* 一直分兩半，再一個個合起來
* 二元樹陣列需開到**4n**(有證明)
* 以下樹的陣列是1-indexed

#define N 100000
int tree[N<<2]={0};
int num[N];

void build(int v, int l, int r){
    if (l == r)
        tree[v]=num[l];
    else{
        int mid = (l+r) >> 1;
        build(v*2, l, mid);
        build(v*2+1, mid+1, r);
        tree[v]=tree[v*2]+tree[v*2+1];
    }
}

void update(int v, int x, int pos, int l, int r){
    if(l==r)
        tree[v]=x;
    else{
        int mid=(l+r)>>1;
        if(pos<=mid) update(2*v, pos, l, mid);
        else update(2*v+1, pos, mid+1, r);
        tree[v]=tree[2*v]+tree[2*v+1];
    }
}

int query(int v, int l, int r, int ql, int qr){
    if(ql>qr)
        return 0;
    if(l==ql && r==qr)
        return tree[v];

    int mid=(l+r)>>1;
    return query(2*v, l, mid, ql, min(qr, mid))+query(2*v+1, mid+1, r, max(ql, mid+1), qr);
}

懶標
---
* 用於區間和
* modify變成跟區間查詢很像，如果要加的區間完全涵蓋某節點的區間，就對那個節點標記要加的值（自己也加起來）
* 而下次要區間查詢或修改，如果遇到又標記的節點，就把它往下推到兩個子節點，並初始化目前節點的標記

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

LL tree[5*500000], num[500010], tag[5*500000]={0};

void push(int v, int l, int r){
	int mid=(l+r)>>1;
	tag[2*v]+=tag[v];
	tag[2*v+1]+=tag[v];
	tree[2*v]+=(mid-l+1)*tag[v];
	tree[2*v+1]+=(r-mid)*tag[v];
	tag[v]=0;
}

void build(int v, int l, int r){
	if(l==r) tree[v]=num[l];
	else{
		int mid=(l+r)>>1;
		build(2*v, l, mid);
		build(2*v+1, mid+1, r);
		tree[v]=tree[2*v]+tree[2*v+1];
	}
}

void modify(int v, int l, int r, int ul, int ur, LL x){
	if(l==ul && r==ur){
		tag[v]+=x;
		tree[v]+=(r-l+1)*x;
		return;
	}
	if(tag[v]) push(v, l, r);
	int mid=(l+r)>>1;
	if(ur<=mid) modify(2*v, l, mid, ul, ur, x);
	else if(ul>mid) modify(2*v+1, mid+1, r, ul, ur, x);
	else{
		modify(2*v, l, mid, ul, mid, x);
		modify(2*v+1, mid+1, r, mid+1, ur, x);
	}
	tree[v]=tree[2*v]+tree[2*v+1];
}

LL query(int v, int l, int r, int ql, int qr){
	if(l==ql && r==qr) return tree[v];
	if(tag[v]) push(v, l, r);
	int mid=(l+r)>>1;
	if(qr<=mid) return query(2*v, l, mid, ql, qr);
	else if(ql>mid) return query(2*v+1, mid+1, r, ql, qr);
	return query(2*v, l, mid, ql, mid)+query(2*v+1, mid+1, r, mid+1, qr);
}