ツリー配列の和と最大値

樹状配列の和と区間最大値を求めるテンプレート
 
iの親子の差lowbit(i)
各C[i]はc[i-1],c[i-2],c[i-4],......c[i-lowbit(i)]からなり、例えばc[8]=c[8-1]+c[8-2]+c[8-4]からなる
区間加算テンプレート

#include 
#include
using namespace std;

const int N = 5e5+50;
int num[N];
int c[N];
int n;

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

void build(int n){
    for(int i = 1; i <= n; ++i)
    {
        c[i] += num[i];
        for(int j = 1; j  0; i-=lowbit(i) )
        sum += c[i];
    return sum;

}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> num[i];
    build(n);
    int temp1, temp2;
    cin >> temp1 >> temp2;
    update(temp1, temp2-num[temp1]);
    int x, y;
    cin >> x >> y;
    cout << query(y)-query(x-1) << endl;
    return 0;
}

 
区間最値テンプレート

#include 
#include
using namespace std;

const int N = 1e5+50;
int num[N];
int c[N];
int n;

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

void build()
{
    for(int i = 1; i <= n; ++i)
    {
        c[i] = num[i];
        for(int j = 1; j < lowbit(i); j<<=1)
            c[i] = max(c[i], c[i-j]);
    }
}

void update(int x)
{
    for(int i = x; i <= n; i+=lowbit(i))
    {
        c[i] = num[i];
        for(int j = 1; j < lowbit(i); j<<=1)//   C[i]  i-j  
            c[i] = max(c[i], c[i-j]);
    }
}

int query(int s, int e)
{
    if(s == e)
        return num[s];
    else
    {
        if((e-lowbit(e)+1) == s)
            return c[e];
        if((e-lowbit(e)+1) > s)
            return max(c[e], query(s, e-lowbit(e)));
        if((e-lowbit(e)+1) < s)
            return max(num[e], query(s, e-1));
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> num[i];
    build();
    int temp1, temp2;
    cin >> temp1 >> temp2;
    num[temp1] = temp2;
    update(temp1);
    cin >> temp1 >> temp2;
    cout << query(temp1, temp2) << endl;
    return 0;
}