树状数组详解
https://blog.csdn.net/sjystone/article/details/115396746

树状数组：

单点加，求区间和
1.快速求前缀和 o(logn)
2.修改某一个数 o(logn)
拓展:区间加，求单点和(见例题简单的整数问题1) -> 结合差分
拓展:区间加，区间求和(见例题简单的整数问题2)

lowbit(x)用于取x二进制最低位的1与后面的0组成的数字
原理：二进制的负数是正数取反加一

int lowbit(int x)
{
    return t & (-t);
}

假设x = 2^ik + 2^ik-1 +...+ 2^i1
ik >= ik-1 >= ... i1
将区间划分成(左开右闭)
(x - 2^i1, x]  包含2^i1个数，2^i1是右边界二进制表示的最后一位1与后面的0构成的数
(x - 2^i1 - 2^i2, x - 2^i1]   包含2^i2个数，2^i2是右边界二进制表示的最后一位1与后面的0构成的数
(x - 2^i1 - 2^i2 - 2^i3, x - 2^i1 - 2^i2]  ...
...
(0, x - 2^i1 - 2^i2 -...- 2^ik-1)  包含2^ik个数，包含2^ik个数，2^ik是右边界二进制表示的最后一位1与后面的0构成的数

-> 对于其中任意区间(L,R] 长度是R的二进制表示的最后一位1所对应的数
-> 则对于其中的每一个区间，可以表示为 [R - lowbit(R) + 1, R]    (左闭右闭)
-> 可以用数组c[R]表示这个区间总和
    -> c[x - lowbit(x) + 1, x]表示以x为右端点，长度为lowbit(x)+1的区间的所有数的和
    -> 对于1～x所有数的和，最多可以拆成logx个c[x]的和

  ---------------------------------------------------------------------c16
  ------------------------------------c8
  ----------------c4                      -------------c12
  ------c2            ------c6            -----c10        -----c14    
  -c1       -c3       -c5       -c7       -c9     -c11    -c13    -c15
a 1    2    3    4    5    6    7    8    9   10  11  12  13  14  15  16

c16  =  a16  +  c15  +  c14  +  c12  +  c8
10000           01111   01110   01100   01000

求x的子节点
先将x减去1（eg 10000变成01111），每个1对应一个儿子(eg 01111 01110 01100 01000)
c[x] = a[x] + c[x-1] + c[x-1-lowbit(x-1)] + c[x-1-lowbit(x-1)-lowbit(x-2)] +...+ 0
    对于x-1-lowbit(x-1)表示将x-1的最后一个一去掉，即实现01111 -> 01110

通过父节点找子节点
    对于x-1，有k个儿子，即循环k次，每次减掉最后的1，即找到每一个儿子
    for ( int i = x - 1; i >= x - lowbit(x); i -= lowbit(i) ) tr[x] += tr[i]
通过子节点找父节点
    更改x的值，即更改(上图)包含x的所区间
    假如x 0011100 -> x父节点p 0100000(唯一的) 0011100 + 0000100 = 0100000
    -> p = x + lowbit(x) -> p2 = p + lowbit(p) -> p3 = ... -> 直到等于n
    最多持续logx次
    for ( int i = x; i <= n; i += lowbit(i) ) tr[i] += c;

tr[i]表示，以i结尾，长度是lowbit(i)的区间内元素的和!!!

初始化树状数组：
1.for ( int i = 1; i <= n; i ++ ) add(i, a[i])
    ->时间复杂度o(nlogn)

////////////////////


楼兰图腾 https://www.acwing.com/problem/content/243/

树状数组 （若数据很大，需要考虑用离散化）

注：y1～yn是1到n的一个排列

对于n个点，划分为n个集合(区间)，对于集合k，是以yk为最低点的满足大小大的方案数量数量（不重不漏）
对于yk，统计yk左右两边各有多少数大于yk，再将两数相乘

从左往右，预处理有多少个点大于yk，数量存在Greater[k]，再从左往右找有多少个数大于yk，将该数与Greater[k]相乘
Lower同理
每处理一个数，就将该数加入集合，对应操作为add(y, 1)

int lowbit(int x)      lowbit函数
{
    return x & (-x);
}

void add(int x, int c)  某个数加c
{
    for ( int i = x; i <= n; i += lowbit(i) ) tr[i] += c;
}

int sum(int x)          求前缀和
{
    int res = 0;
    for ( int i = x - 1; i; i -= lowbit(i) ) tr[x] += tr[i];
    return res;
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200010;
int Greater[N], Lower[N], a[N], n, tr[N];
long long res1, res2;

int lowbit(int x)
{
    return x & (-x);
}

void add(int x, int c)
{
    for ( int i = x; i <= n; i += lowbit(i) )
        tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for ( int i = x - 1; i; i -= lowbit(i) )
        res += tr[i];
    return res;
}

int main()
{
    cin >> n;
    for ( int i = 1; i <= n; i ++ ) cin >> a[i];
    for ( int i = 1; i <= n; i ++ )     //从左往右，预处理比y大/小的数的个数
    {
        int y = a[i];
        Greater[i] = sum(n) - sum(y);
        Lower[i] = sum(y - 1);
        add(y, 1);                      //每次处理，都要将该数加入集合
    }
    memset(tr, 0, sizeof tr);           //清空tr
    for ( int i = n; i; i -- )          //从右往左，找比y大/小的数的个数，乘预处理的个数
    {
        int y = a[i];
        res1 += Greater[i] * (long long)(sum(n) - sum(y));
        res2 += Lower[i] * (long long)(sum(y - 1));
        add(y, 1);
    }
    cout << res1 << ' ' << res2;
    return 0;
}