LeetCode 307. Range Sum Query -

#include<stdio.h>
#include<stdlib.h>
/**
 * LeetCode 307. Range Sum Query - Mutable
 * 区间求和，单点修改问题
 * 其解决方法主要为树状数组和线段树
 *
 * 此代码使用树状数组
 *
 * 两点需要注意：
 * 1.树状数组下标从 1 开始，题目中数据数组从 0 开始
 *      解决：index 整体 +1 即可
 * 2.树状数组支持单点增加，此题为单点修改。
 *      newVal = oldVal + (newVal - oldVal)
 *      每增加 newVal - oldVal 即可
 */
#define LOWBIT(x) ((x)&(-(x)))

typedef struct {
    int *C;
    int numOfData;
    int *nums;
} NumArray;


int getSumRange( int *nums,int x,int y ){
    int res = 0,i;
    for( i=x;i<=y;i++ ){
        res += nums[i];
    }
    return res;
}

int getCI(int *nums,int S){
    int seart = S - LOWBIT(S) + 1;
    int res = getSumRange(nums,seart-1,S-1);
    return res;
}

NumArray* numArrayCreate(int* nums, int numsSize) {
    NumArray* res = (NumArray*)malloc(sizeof(NumArray));
    res->numOfData = numsSize;
    res->C = (int*)malloc(sizeof(int)*(numsSize+1));
    res->nums = nums;

    int i;
    for( i=1;i<=numsSize;i++ ){
        // 初始化 树状数组
        res->C[i] = getCI(nums,i);
    }
    return res;
}

void real_numArrayUpdate(NumArray* obj, int i, int val){
    while(i <= obj->numOfData){
        obj->C[i] +=val;
        i += LOWBIT(i);
    }
}

void numArrayUpdate(NumArray* obj, int i, int val) {
    // 对第 2 点的处理
    real_numArrayUpdate(obj,i+1,val - obj->nums[i]);
    obj->nums[i] = val;
}

int getSum( NumArray* obj, int i ){
    int res=0;
    while( i>0 ){
        res += obj->C[i];
        i -= LOWBIT(i);
    }
    return res;
}

int real_numArraySumRange(NumArray* obj, int i, int j) {
    return getSum(obj,j) - getSum(obj,i-1);
}

int numArraySumRange(NumArray* obj, int i, int j){
    // 对第 1 点的处理
    return real_numArraySumRange(obj,i+1,j+1);
}


void numArrayFree(NumArray* obj) {
    free(obj->C);
    free(obj);
}

int main() {

    int nums[] = {1, 3, 5};
    int len = 3;

    NumArray* numArray = numArrayCreate(nums,len);
    printf("%d\n",numArraySumRange(numArray,0,2));
    numArrayUpdate(numArray,1,2);
    printf("%d\n",numArraySumRange(numArray,0,2));
    numArrayFree(numArray);
    return 0;

}

另一解使用线段树
LeetCode 报如下错：
Line 40: Char 5: runtime error: signed integer overflow: 1073741824 * 2 cannot be represented in type 'int' (solution.c)

（代码对应位置已打注释）

奇怪的是，笔者电脑跑相同的数据却正常，leetcode 中 test case 测试相同的数据也正常。

leetcode报错.png leetcode test case 正常.png 笔者电脑测试.png

目前还不知道为什么会出现 int 溢出，觉得在仅仅输入3个数据的情况下，代码并不会溢出。

代码如下：

typedef struct {
    int *nums;
    int *S;
    int numsSize;
} NumArray;

void _test_printS( NumArray* o ){
    int i;
    for( i=1;i< 4*(o->numsSize);i++ ){
        printf("The %d:%d\n",i,o->S[i]);
    }
}

void _test_print_numsData( int *nums,int size ){
    printf("nums data:");
    for( int i=0;i<size;i++ ){
        printf("%d ",nums[i]);
    }
    printf("\n");
}

int _getNumsData( NumArray* o,int i ){
    return o->nums[i-1];
}

void _buildTree( NumArray* o,int l,int r,int index ){

    static int times = 0;

    if( l == r ){
        o->S[index] = _getNumsData(o,l);
        return;
    }



    int m = (l+r)/2;
    printf("The %d times -> l:%d, r:%d,index:%d, m:%d\n ",times++,l,r,index,m);
    _buildTree( o,l,m,index*2 );//报错
    printf("1\n");
    _buildTree( o,m+1,r,2*index+1 );
    printf("2\n");
    o->S[index] = o->S[index*2] + o->S[index*2+1];
}

NumArray* numArrayCreate(int* nums, int numsSize) {

    _test_print_numsData( nums,numsSize );

    NumArray *res = (NumArray*)malloc(sizeof(NumArray));
    res->S = (int*)malloc((numsSize*4+1)* sizeof(int));
    memset(res->S,0,(numsSize*4+1)* sizeof(int));
    res->numsSize = numsSize;
    res->nums = nums;
    // printf("The %d",numsSize);
    _buildTree(res,1,numsSize,1);
    return res;
}

void _add( NumArray* obj,int ind,int ind_l,int ind_r, int i, int val ){
    obj->S[ind] += val;
    if( ind_l == ind_r )return;
    int m = (ind_l+ind_r)/2;
    if( ind_l <= i && i <= m ){//left
        _add( obj,ind*2,ind_l,m,i,val );
    } else{//right
        _add(obj,ind*2+1,m+1,ind_r,i,val);
    }
}

void numArrayUpdate(NumArray* obj, int i, int val) {
    _add(obj,1,1,obj->numsSize,i+1,val - obj->nums[i]);
    obj->nums[i] = val;
}

int _getRangeSum( NumArray* obj,int index,int ind_l,int ind_r,int l,int r ){
    if( ind_l == l  &&  ind_r == r ){
        return obj->S[index];
    }

    int m = (ind_l+ind_r)/2;
    //  跨区间
    if( l <= m && r >m ){
        return _getRangeSum( obj,2*index,ind_l,m,l,m ) +
               _getRangeSum( obj,2*index+1,m+1,ind_r,m+1,r );
    } else if( r <= m ){
        // 全在左区间
        return _getRangeSum( obj,2*index,ind_l,m,l,r);
    } else{
        // 全在右区间
        return _getRangeSum( obj,2*index+1,m+1,ind_r,l,r);
    }

}

int _real_numArraySumRange(NumArray* obj, int i, int j){
    return _getRangeSum( obj,1,1,obj->numsSize,i,j );
}

int numArraySumRange(NumArray* obj, int i, int j) {
    return _real_numArraySumRange(obj,i+1,j+1);
}

void numArrayFree(NumArray* obj) {
    free(obj->nums);
    free(obj);
}