树状数组

标签：范围查询   include   ons   one   ace   syn   否则   std   ble   

#include 

using namespace std;
typedef long long ll;
typedef pair ii;
typedef vector vi;
typedef vector vii;
typedef vector vll;
const int INF = 0x3f3f3f3f;
const long long LLINF = 4e18;
const double EPS = 1e-9;
const int maxn = 1e6 + 10;

#define LSOne(S) ((S) & -(S))  //不加括号会导致结果出错，具体原因见P45
int n;
int ft[maxn], ft_extra[maxn];  //ft数组用于存储一个传统的树，ft_extra数组用于区间修改+区间查询时存储的另一颗树
int f[maxn];                   //f数组用于存放题目输入的数据或输入数据的差分数组
int a[maxn];

ll rsq(ll i) {                 //求f[1]到f[i]的和，若f为差分数组则此功能为 point_query单点查询f[i]
    ll sum = 0;
    for (; i; i -= LSOne(i)) sum += ft[i];  //从后往前加，每次减去一个 LSOne(i)（二进制截取最后一位1）
    return sum;
}

ll pq_range(ll n) {            //用于计算（n+1）f[i] - i*f[i] 的前n项和
    ll sum = 0;
    for (int i = n; i; i -= LSOne(i)) sum += (n + 1) * ft[i] - ft_extra[i];
    return sum;
}

ll rsq_range(ll l, ll r) {     //range_query 范围查询，习惯上用l作为左端点，r作为右端点, f必须为差分数组
    return pq_range(r) - pq_range(l - 1);
}

void update(int i, ll v) {                //单点更新
    for (; i > n;

    for (int i = 1; i > a[i];
        f[i] = a[i] - a[i - 1];  //将f建立为输入数据的差分数组
    }
    cout 

树状数组

标签：范围查询   include   ons   one   ace   syn   否则   std   ble   

原文地址：https://www.cnblogs.com/xiezeju/p/14454748.html